WC '17 Contest 3 S2 - GleamingProudChickenFunRun

View as PDF

Points: 12 (partial)
Time limit: 2.75s
Memory limit: 128M

Author:
Problem type
Woburn Challenge 2017-18 Round 3 - Senior Division

You've assembled a set of Twitch clips from a live stream by your favourite twitch.tv streamer. A clip is a video fragment of the stream, and the -th clip encapsulates the exclusive time interval from to seconds into the stream . The clips are not all guaranteed to be distinct.

In an effort to convince your friends to start watching this stream and join you in spamming its chat, you plan to show them some of the clips. You'd like to choose the smallest possible subset of the clips which still offer a good representation of the whole stream. In particular, each of the total clips must have some time in common with at least one clip in . A pair of clips have some time in common with each other if there's a positive amount of time from the stream which is present in both clips - in other words, if the intersection of their exclusive time intervals is non-empty. For example, clips with time intervals and have some time in common, while clips with time intervals and do not.

Can you determine the minimum possible number of clips which can be made up of?

In test cases worth of the points, .
In test cases worth another of the points, .

Input Specification

The first line of input consists of a single integer, .
lines follow, the -th of which consists of two space-separated integers, and , for .

Output Specification

Output a single integer, the minimum possible number of clips which can be made up of.

Sample Input

6
11 14
14 23
5 22
12 28
2 6
22 31

Sample Output

2

Sample Explanation

No single clip can be chosen such that all other clips have some time in common with it. However, there are various valid sets made up of clips, such as clips and .