QUCOLCM - Editorial

editorial
, ,
1

PROBLEM LINK

Contest

Practice

Author: grebnesieh

Tester: krooonal

DIFFICULITY

Easy

PREREQUISITES

Greedy

PROBLEM

Given a set of intervals, find the size of the largest subset such that no two of them intersect.

EXPLANATION

Got the idea for this one while attended my first Waves festival. Granted I did not intend to attend all the events, but I had just started competitive coding and this seemed like a good potential problem.

Turns out its pretty common. Interval Scheduling Maximization

Brief explanation:

  1. Sort in increasing order of ending time.
  2. Select the first interval.
  3. Remove all those which intersect with the selected interval.
  4. Select the next interval. If none left, break.
  5. Back to Step 3.

The number of intervals you “selected” is your answer.

O(n logn) overall complexity.

Without further ado, the code:

for _ in xrange(input()):
    events = []
    for __ in xrange(input()):
        start, end = map(int, raw_input().split())
        events.append((end, start))
    events.sort()
    ans = 0
    minstart = -1
    for end, start in events:
        if start > minstart:
            ans += 1
            minstart = end
    print ans
1 Like
2

What if n=3, 0 5, 1 2, 3 4…the answer should be 2 but according to above solution answer is 1.

3

My bad. I incorrectly wrote “Sort in decreasing order of ending time.” I have fixed it and now it reads “Sort in increasing order of ending time.” Which gives correct answer. (1, 2), (3, 4), (0, 5) You can select the first two.

Once again, sorry for the mistake. I guess I need some sleep. xD

4

My Code is running fine with all the test cases.But still gives WA.Any corner cases ?