Time limit 4000/7000/7000/7000 ms. Memory limit 65000/65000/65000/65000 Kb.
Prepared by Ibrahim Mesecan.
Guest Room Usage
Shqip
There is one special guest room at the university. But, there are many professors want to use it. The administration
wants to prepare a program to find out the maximum usage. They have stored the start and end times of all activities of professors.
Write a program to find out at most how many professors can use the room without any overlaps.
Input specification
The first line has number (n) which shows the number of professors who want to use the room
where 2 ≤ n ≤ 20000. The following n lines contain two numbers each (p and q) where p stands for
the start time and q stands for the end time of the current activity, where 1 ≤ p < q ≤ 40000.
Output specification
Show the maximum number of usage without any overlapping times.
Sample Input:
11
0 6
1 4
8 13
3 5
8 12
3 8
5 9
6 10
5 7
2 13
12 14
|
Sample Output:
4
|
Output Explanation:
According to the given list, at most 4 activities can use the room without any overlaps.
(For example the following activities can be selected without any overlaps)
- Activity 2 starts at 1 and finishes at 4
- Activity 9 starts at 5 and finishes at 7
- Activity 5 starts at 8 and finishes at 12
- Activity 11 starts at 12 and finishes at 14
Note: Please note that there can be several activity combinations giving the same (4) result.
Just, give the Max number.
Для отправки решений необходимо выполнить вход.
|