For this year’s Hack Week, our team built a TV channel on IGN. IGN has a ton of video content, but you had to find it yourself. There wasn’t a place where you could just tune in and have interesting videos play automatically, so we built it. Scratch your own itch, right?
One of the core pieces of the project was scheduling videos that fit a particular theme into a fixed time slot. For example, we wanted to show 15 minutes of news videos starting at 6pm. Unlike traditional TV where the content is made to fit into pre-determined time slots, we were picking from videos that varied in length. We knew segments would not end exactly on time, but we wanted the overflow to be as small as possible so the next segment would start as close to on-time as possible.
There was also a matter of prioritization. Some videos, like our daily news show, should always make it into our news segment. Fresher content should be prioritized over older content. And in the future, we might want to take the popularity of videos into consideration as well.
Essentially, we had to solve a variation of the knapsack problem. Unfortunately,
The decision problem form of the knapsack problem (“Can a value of at least V be achieved without exceeding the weight W?) is NP-complete, thus it is expected that no algorithm can be both correct and fast (polynomial-time) on all cases.
Fortunately, for our purposes, we didn’t have to find the correct solution, just a solution that was good enough.