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.
No comments:
Post a Comment