HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC - 2013-2014 > problem:


2013-03-40. 50685 - Guest Room Usage

IMPC - 2013-2014

Start: Mar.16.2013 at 12:00:00 PM
Finish: Mar.16.2013 at 05:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 14-05-95. 50479 - Bit Compressor
• 14-07-10. 50383 - Noisy Mornings
• 14-07-20. 50384 - Permutations revi...
• 14-07-30. 50385 - The 3n + 1 problem
• 14-07-50. 50367 - Bar Codes
• 2013-03-10. 50579 - Pentagonal Nu...
• 2013-03-20. 50589 - The Number of...
• 2013-03-30. 50559 - Prime Factors ...
• 2013-03-40. 50685 - Guest Roo...
• 2013-04-10. 50335 - Five Math Ope...
• 2013-04-100. 50323 - Filtering Cont...
• 2013-04-30. 50337 - Exam Averages
• 2013-04-40. 50338 - Convert Into ...
• 2013-04-50. 50774 - Hot Potato
• 2013-04-70. 50296 - Total Discount...
• 2013-04-80. 50343 - The number of...
• 2013-04-90. 50332 - Variance of a ...

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