|Scheduling Problem by Hideki HASHIMOTO|
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.