LCC/Moose '18 Contest 3 S2 - Delivering Presents

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

On Christmas Eve, Santa faces an incredibly difficult logistical challenge: in one night, he must deliver presents to hundreds of millions of children worldwide. In order to have more time to deliver presents, Santa makes use of kids' sleeping schedules. He knows when they are sleeping and knows when they're awake, so with a careful ordering, he can come before they wake.

Specifically, there are N children that Santa is delivering presents to. Each child has a bed time and wake time between which Santa must deliver their present. Santa takes one unit of time to deliver a present to a child.

Santa wants to know the maximum number of kids that he will be able to deliver presents to.

Input Specification

The first line of input contains one integer N (1 \le N \le 5 000), the number of kids that Santa is planning to deliver presents to.

The next N lines will each contain two integers B and W (1 \le B < W \le 50), the bed-time and wake time of a child.

Output Specification

The maximum number of presents that Santa will be able to deliver.

Sample Input 1

5
1 2
1 3
2 4
4 5
4 5

Sample Output 1

4

Sample Input 2

3
1 2
2 3
3 4

Sample Output 2

3

Comments

There are no comments at the moment.