Hello,
This is an interesting question...one that I have been battling with for a few days now.
I am writing a program to schedule jobs on computers. (All hypothetical). The jobs are listed with start and end times, and the computers that they may be run on.
The goal is to schedule as many of these jobs as possible. I have solved it by writing a recursive function that calls itself by scheduling every job on each of its potential computers and not schdeduling it, then recursing to all remaining jobs. In an effort to cut runtime, I am pruning my recursive call tree by not attempting to schedule a job which conflicts with an already scheduled job.
This is where my question comes into play: I know there is a way to check for job conflicts in a constant amount of time, but I can't figure out how. Currently, I have a vector for each computer, of which the elements are items representing the jobs that have been scheduled on that computer. These jobs have their start/end times listed. So, to check for a collision, I am iterating through the computer vector, and checking each element's start/end times to see if there exists a conflict with the job that I am attempting to schedule.
Does anyone have a suggestion on how I may use a better data structure, or some other method to detect if a collision exists?
Thanks!