Given a set of intervals, find the size of the largest subset such that no two of them intersect.
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
- Sort in increasing order of ending time.
- Select the first interval.
- Remove all those which intersect with the selected interval.
- Select the next interval. If none left, break.
- 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