PROBLEM LINK
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:
- 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