Hardcore Grinding

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 256M

Problem types

friendly304010 really likes to grind (and somehow she manages it well), but can she finish all her tasks, just by herself? The answer, is sadly no. During the grade 9 year, she was doing fine, but in terms of computer science, she seems to be lacking a bit behind in her homework.

In order to combat this, she has machines to do the work for her! She has N tasks (computer contest homework), and she wants to know how many machines she needs to complete the task, as each machine costs quite a fortune. Each task has a start time s_i and an end time f_i, each machine cannot do more than 1 task at a time.

friendly304010 is stuck on the problem. You, as her trusty programmer, shall help her and solve her dilemma.

Input Specification

First line N, denoting the number of tasks that friendly304010 needs to do.

Next N lines, 2 integers s_i and f_i, denoting the start time and finish time of the i^\text{th} task. The tasks are sorted in order by start time.

Output Specification

Output one integer, the total number of machines that are required to finish all N tasks, such that each machine does only 1 task at a time.


  • 1 \le N \le 10^6
  • 1 \le s_i < f_i \le 10^7
  • s_i \ne f_i
  • Tasks occupy the range [s_i, f_i)

Sample Input

1 3
1 4
2 5
3 7
4 7
6 9
7 8

Sample Output


Explanation of Sample


There are no comments at the moment.