Home /
Expert Answers /
Computer Science /
exercise-interval-coloring-consider-the-following-greedy-algorithm-for-interval-coloring-1-use-pa633
(Solved): Exercise Interval Coloring - Consider the following greedy algorithm for interval coloring: 1. Use ...
Interval Coloring - Consider the following greedy algorithm for interval coloring: 1. Use the algorithm for interval scheduling to find the maximum subset of jobs with no conflict, 2. give all of them the same color, 3. remove them from the set 4. and repeat. - Exercise: find a counter-example
Expert Answer
Definitions : Interval Scheduling : Given a sequence of intervals, choose a subset of intervals of maximum size which do not conflict with each other