### 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
```