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.


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 should consist of a single integer: the minimum number of shots required to photograph every budgie at least once.

Sample Input 1

0 2
2 4
5 7
6 9
8 10

Sample Output 1


Sample Input 2

60 240
13 37

Sample Output 2



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.



Privacy statement
© Australian Mathematics Trust 2001-2023

Page generated: 21 September 2023,  9:59pm AEST