Woburn Challenge 2017-18 Round 3 - Senior Division

Problem 2: GleamingProudChickenFunRun

You've assembled a set of N (1 ≤ N ≤ 300,000) Twitch clips from a live stream by your favourite twitch.tv streamer. A clip is a video fragment of the stream, and the i-th clip encapsulates the exclusive time interval from A_i to B_i seconds into the stream (0 ≤ A_i < B_i ≤ 10⁹). 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 S of the clips which still offer a good representation of the whole stream. In particular, each of the N total clips must have some time in common with at least one clip in S. 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 (0, 5) and (4, 10) have some time in common, while clips with time intervals (0, 5) and (5, 10) do not.

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

Subtasks

In test cases worth 5/23 of the points, N ≤ 15.
In test cases worth another 11/23 of the points, N ≤ 1000.

Input Format

The first line of input consists of a single integer, N.
N lines follow, the i-th of which consists of two space-separated integers, A_i and B_i, for i = 1..N.

Output Format

Output a single integer, the minimum possible number of clips which S 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 5 other clips have some time in common with it. However, there are various valid sets S made up of 2 clips, such as clips 4 (12..28) and 5 (2..6).

All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 6.00s
Memory Limit: 128M
Added: Mar 23, 2018
Author: Alex

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)