CODEWITHSUNDEEP
algorithm
dangerChihuahua007
dangerChihuahua007

Reputation: 20895

Does greedily removing intervals with most conflicts solve interval scheduling?

We can solve the scheduling problem, in which we must select the largest set of continuous intervals that do no overlap, with a greedy algorithm: we just keep picking the intervals that end the earliest: http://en.wikipedia.org/wiki/Interval_scheduling

Apparently, greedily picking the intervals with fewest conflicts does not work.

I was wondering if putting all the intervals in one big set and then greedily removing the interval with the most number of conflicts left (until the intervals have no conflicts) works. I can envision implementing this greedy algorithm with a priority queue: every time we remove the interval X with greatest conflicts from the priority queue, we update the other intervals that used to conflict with interval X so that the other intervals now are marked as having 1 less conflict.

Does this work? I'm trying to come up with a counterexample to disprove it and can't.

Upvotes: 6

Views: 1809

Answers (2)

Christian Rudder
Christian Rudder

Reputation: 71

The counter example is

==== ==== ==== ====
   ---  xxx  ---
   ---       ---
   ---       ---

We want the (====) bars, but the (xxx) breaks sorting by fewest conflicts, as when it's picked, it stops the middle two (====) from ever being selected.

Upvotes: 0

Gassa
Gassa

Reputation: 8846

Here is a counterexample. The idea is to drop a required interval on the very first pick. The number of conflicts is on the right.

        ====    2
       ----     3
      ----      3
    ====        4
  ----          3
 ----           3
====            2

Obviously, we will want to pick the three bold (====) intervals and drop the four thin (----) intervals. There is no other way to obtain three non-intersecting intervals.

By the way, you may find the TopCoder tutorial on greedy problems interesting since it starts with a discussion of several approaches on the same problem.

Upvotes: 5

Related Questions