The concept behind Interval Scheduling Greedy Algorithm is that we have a set of jobs (tasks) that need to be scheduled on a machine, and each job j has a start time Sj and a finish time Fj. We can’t schedule two jobs at the same time if they overlap. Our objective is to fill our machine with as many jobs as possible. Wikipedia definition of Interval-Scheduling-Greedy-Algorithm HERE.
Example
Consider the following five work intervals: [1, 3], [2, 4], [3, 5], [4, 6], [5, 7]. Then, the three jobs [1, 3], [3, 5], and [5, 7] should be scheduled. Any other option will only schedule two jobs.
Let’s have a look at a few greedy algorithms that don’t work. Let’s see if we can come up with some counter-examples for each one. “candidate job” doesn’t clash with any other planned work.
To read more visit https://hecodesit.com/interval-scheduling-greedy-algorithm/
Top comments (0)