AIOC Banner

Problem: Budgie Shots

Want to try solving this problem? You can submit your code online if you log in or register.


Budgie Shots

Input File: shotin.txt
Output File: shotout.txt
Time Limit: 1 second
Memory Limit: 8 MB


There are N budgies down in your garden each day,
who eat seeds from the ground and sit up on the wall.
You would like to use your shiny camera to
take some colourful photographs (shots) of them all.

You have watched the birds closely and know them quite well.
You know each of the budgies can only be seen
at a certain fixed interval every day
when that budgie emerges, all feathered and green.

You can photograph multiple budgies at once
and/or one budgie multiple times, if that's best.
If a budgie flies in or out right when you shoot
you will capture it still (so please don't feel too stressed!).

Now, you want to shoot every bird at least once,
but your film is expensive - try keeping costs low!
Finding out the least number of shots you must take
is your task in this part of the AIIO.

Input

The first line of input will contain the single integer N (1 ≤ N ≤ 100,000), the number of budgies. The following N lines will describe the times when each budgie is visible (and hence able to be photographed). The i'th of these lines will contain two integers ai and bi, describing the time (in minutes past sunrise) when the i'th budgie flies in and out of view, respectively. You are guaranteed that 0 ≤ ai < bi ≤ 2,000,000,000.

Output

Output should consist of a single integer: the minimum number of shots required to photograph every budgie at least once.

Sample Input 1

5
0 2
2 4
5 7
6 9
8 10

Sample Output 1

3

Sample Input 2

2
60 240
13 37

Sample Output 2

2

Explanation

In the first example, you require at least three photos to capture all the budgies. Here is one way:

In the second example, the budgies appear at completely different times. You have no choice but to take a new photo for each budgie.

Subtasks

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 15 November 2019,  5:54am AEDT