Problem: Budgie Shots
Want to try solving this problem? You can submit your code online if you log in or register.
Input File: shotin.txt
Output File: shotout.txt
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
Sample Output 1
Sample Input 2
Sample Output 2
In the first example, you require at least three photos to capture all the
budgies. Here is one way:
- Take a photo at time t=2 minutes, capturing budgies 1 and 2.
- Take a photo at time t=6 minutes, capturing budgies 3 and 4.
- Take a photo at time t=9 minutes, capturing budgies 4 and 5.
In the second example, the budgies appear at completely different
times. You have no choice but to take a new photo for each budgie.
- For Subtask 1 (45 points), N ≤ 1000.
- For Subtask 2 (55 points), no further constraints apply.