Classroom assignment

Interview

Time limit1sMemory limit256 MB

Summary

Given N class time intervals, find the smallest number of rooms so overlapping classes never share a room.

Level: Medium4 of 10
Topics: Greedy, Sorting, Heap, Intervals
Solved: No attempts yet

Problem

You are given the timetable of $N$ classes. Class $i$ starts at time $S_i$ and ends at time $T_i$ . Find the smallest number of classrooms that lets every class run.

One classroom holds at most one class at any moment. The next class may start at the exact time the previous one ends, so if $T_i \le S_j$ , then class $i$ and class $j$ can share a classroom.

Input

The first line contains the number of classes $N$ . ( $1 \le N \le 2 \times 10^5$ )

Each of the next $N$ lines contains $S_i$ and $T_i$ , separated by a space. ( $0 \le S_i < T_i \le 10^9$ )

Output

Print the minimum number of classrooms needed to run every class.

Examples6

Example 1
Input
```
3
1 3
2 4
3 5
```
Expected output
```
2
```
Example 2
Input
```
1
0 1000000000
```
Expected output
```
1
```
Example 3
Input
```
4
0 1
1 2
2 3
3 4
```
Expected output
```
1
```
Example 4
Input
```
5
7 9
7 9
7 9
7 9
7 9
```
Expected output
```
5
```
Example 5
Input
```
4
0 100
10 20
15 25
30 40
```
Expected output
```
3
```
Example 6
Input
```
3
0 5
5 10
4 6
```
Expected output
```
2
```