The observation timetable
Statement
An observatory has only one telescope. Researchers wanting to use it handed in N observation request forms, and each form has the time the observation starts and the time it ends written on it as integers.
With only one telescope, two observations cannot run at the same time. Starting another observation at the very moment one observation ends is allowed, though. Moving or cooling the telescope is taken to need no time. The times written on a form cannot be changed, so accepting a request means running it at exactly the times written. Some forms have the same start time and end time, and such an observation takes no time at all.
The person in charge of the observatory wants to accept as many forms as possible. Given the N request forms, write a program that finds the largest number of observations that can run without overlapping.
For example, suppose the N=11 request forms are the ones in the following table.
| Form | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Start time | 1 | 3 | 0 | 5 | 3 | 5 | 6 | 8 | 8 | 2 | 12 |
| End time | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
Accepting form 1, form 4, form 8 and form 11 lets four observations run without overlapping.
| Accepted form | 1 | 4 | 8 | 11 |
|---|---|---|---|---|
| Start time | 1 | 5 | 8 | 12 |
| End time | 4 | 7 | 11 | 14 |
Observation 1 ends at 4 and observation 4 starts at 5, observation 4 ends at 7 and observation 8 starts at 8, and observation 8 ends at 11 and observation 11 starts at 12. No two observations overlap in time.
There is no way to pick five forms. In this example every form takes a time of 2 or more and even the earliest one ends at 4, so chaining five together cannot leave the last observation ending earlier than 12. Only form 9, form 10 and form 11 end at 12 or later, and whichever of those goes last, four forms cannot be chained in front of it. So the answer in this example is 4.
Input and output examples
Example 1
Input
11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14
Output
4
Example 2
Input
5 679 684 63 97 496 530 23 66 448 492
Output
4
Example 3
Input
1 292 314
Output
1
Input
The first line gives the number of request forms N. N is a natural number from 1 to 100,000.
From the second line through the (N+1)th line, the request forms are given, one form per line. Each line gives the time the observation starts and then the time it ends, separated by one space. Both times are integers from 0 to 1,000,000,000, and the start time is less than or equal to the end time.
Output
Print the largest number of observations that can run without overlapping on the first line.
Print one number and then a newline. Do not add any other character or space before or after it.
Requirements
- Read the input from standard input and write the answer to standard output
- Starting another observation at the very moment one observation ends is allowed
- Forms with the same start time and end time are given as well. Such an observation takes no time, so it can be accepted together with another observation that ends at that same time
- The times written on a form cannot be changed. An accepted observation runs at exactly the times written
- N goes up to 100,000, so checking every subset of the forms does not finish in time
- The output is one number and a newline, nothing else
- Grading compares the output with the expected value down to the last character
- You must write a program that reads from standard input and writes to standard output
- Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
- The languages you can use are Python and JavaScript
- The memory limit is 256MB. The browser does not measure it, it only states it
- The time limit is set by measuring the setter's reference solution on the same runtime
- On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
- There are 15 cases, and 3 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
- You have to pass all 15 cases to solve this.
Examples
3 public cases. Judging also uses hidden cases. You have to pass all 15 cases to solve this.
1 292 314
1
5 679 684 63 97 496 530 23 66 448 492
4
11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14
4
Solution
Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.
Submitting requires you to log in. Running against the public cases works without one.
You can test with 3 public cases. Submitting runs the hidden cases too.
People who solved this problem
The time shown is the time spent solving. Input reading time is outside the solver's control, so it is excluded. And since each device reports this value itself, we record which device measured it.
Log in and you can see the code once you solve this problem.