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 Ai to Bi seconds into the stream (0 ≤ Ai < Bi ≤ 109). 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?
In test cases worth 5/23 of the points, N ≤ 15.
In test cases worth another 11/23 of the points, N ≤ 1000.
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, Ai and Bi, for i = 1..N.
Output a single integer, the minimum possible number of clips which S can be made up of.
6 11 14 14 23 5 22 12 28 2 6 22 31
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).
Point Value: 12 (partial)
Time Limit: 6.00s
Memory Limit: 128M
Added: Mar 23, 2018
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3