Scheduling Problem

Scheduling Problem by Hideki HASHIMOTO

I was working on a programming puzzle over at Coding Games dot com and I wasn't getting anywhere. The problem involved packing as many events as possible into a given time frame. Each event has a start time and a duration and there is a whole raft of them, many more than could possibly fit. Your mission, Jim, should you choose to accept it, is to pick and choose from this raft of possibilities so that you can get the most events on the schedule. It's kind of a make believe problem, because you are going to be charging for the amount of time each event occupies, so it doesn't really matter whether you schedule one job or three as long as they generate the same amount of revenue. But then things are never that simple. There's always the special case where somebody's nephew just has to be on the schedule, or we get brownie points on some big shot's benchmark for having the most number of events, never mind the extra wear and tear on the facilities from all the set up and tear down. So it's kind of arbitrary, but it's also the kind of thing you could run into in real life.
     I sit down and start writing some code. My first attempt is to exhaustively test all possible combinations. That works fine for the first couple of tests where there are only a handful of events to schedule, but it falls flat when the number of events goes up to something like 15,000. Okay, brute force isn't going to work, so I try a couple of schemes and one of them seems like it is getting close to the 'correct' answer, but then I'm kind of stuck. I turn to Google, and lo and behold, Wikipedia has a whole bunch of pages about scheduling algorithms. I poke around for a bit and then I notice Activity selection problem, which sounds suspiciously like the problem I am working on. I skim the article which is basically incomprehensible because of the cryptic notation used that is supposed to mean something, but then I notice the phrase 'Sort the set of activities by finishing time'. Okay, I haven't tried that specifically, so I do, and presto! We have a solution. Actually the solution requires picking the next activity that starts after the current on finishes. You just march down the list picking the next event that that we can accomadate.