CODEWITHSUNDEEP
algorithmintervalsgreedy
maria
maria

Reputation: 21

Alternative greedy strategy to finding points in intervals: does this approach work?

I'm trying to solve the following problem:

You are given a collection of intervals. Find the smallest number of points such that each interval contains at least one point.

I know that one solution to this problem is to sort the intervals by their end time, then to greedily repeatedly pick the endpoint of the earliest interval not yet covered and add that to the result.

However, it also got to my mind that it could be solved by choosing the point which eliminates more intervals at once. I know this idea is not correct, but I cannot find any counterexample. Can someone help me find a counterexample to this strategy?

Upvotes: 2

Views: 327

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59144

Counterexample:

[-----]         [-----]
[------------]
        [-------------]
[------------]
        [-------------]

Upvotes: 3

Mahmood Darwish
Mahmood Darwish

Reputation: 546

Here's an example assuming the intervals are inclusive.

Take intervals:

[1, 4], [2, 5], [3, 6], [4, 7], [5, 8], [5, 9], [5, 10], [8, 12]

Greedy will put a point in 5 as it has the most intervals (all of them except two) Then it will put a point somewhere in the interval [1, 4] and another in the interval [8, 12].

Greedy's answer is 3. But the optimal way is to put one point in 4 and one point in 8 and they all will be covered.

Edit: draw the intervals on a paper for better understanding.

Upvotes: 3

Related Questions