HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50685 - Guest Room Usage

Guest
• Review clarifications (1)

Section problems

• 50488 - Connecting Wires
• 50681 - Center of a Series
• 50561 - Lucky tickets
• 50598 - Minimum Sum
• 50601 - Increasing sequence
• 50613 - Zapakovka
• 50680 - Triangle
• 50683 - Parking Buses
• 50685 - Guest Room Usage
• 50544 - Stock market
• 50545 - Diet

Feedback

If you notice incorrect translations in Contester, please let author know.

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.


Для отправки решений необходимо выполнить вход.

www.contester.ru