NOI '16 P4 - Interval

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 3.0s
Memory limit: 256M

Problem type

There are n closed intervals [l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]. You need to choose m intervals such that the m intervals have nonempty intersection. In other words, there exists some x such that for any selected interval [l_i, r_i], l_i \le x \le r_i.

The cost of selecting a collection of m intervals with nonempty intersection is the maximum length of the m intervals minus the minimum length of the m intervals. The length of interval [l_i, r_i] is r_i-l_i.

Compute the minimum cost of choosing m intervals with nonempty intersection. If this is impossible, output -1.

Input Specification

The first line consists of two positive integers n, m separated by a single space where n is the total number of intervals and m is the number of intervals we are going to choose. It is guaranteed that 1 \le m \le n.

In the following n lines, each line consists of two integers l_i, r_i separated by a space denoting the left and right endpoints of an interval.

Output Specification

Output a line with an integer denoting the minimum cost.

Sample Input 1

6 3
3 5
1 2
3 4
2 2
1 5
1 4

Sample Output 1

2

Explanation for Sample 1

When n = 6, m = 3, the optimal solution is to choose intervals [3, 5], [3, 4], [1, 4]. 4 is contained in all three intervals. The longest interval is [1, 4] and the shortest interval is [3, 4], so the cost should be (4-1)-(4-3) = 2.

Attachment Package

The samples are available here.

Additional Samples

For sample 2: see ex_interval2.in for sample input and ex_interval2.ans for sample output.

For sample 3: see ex_interval3.in for sample input and ex_interval3.ans for sample output.

Constraints

Test casen =m=l_i, r_i
12090 \le l_i \le r_i \le 100
210
319930 \le l_i \le r_i \le 100\,000
4200
51\,0002
62\,000
7199600 \le l_i \le r_i \le 5\,000
820050
90 \le l_i \le r_i \le 10^9
101\,9995000 \le l_i \le r_i \le 5\,000
112\,000400
125000 \le l_i \le r_i \le 10^9
1330\,0002\,0000 \le l_i \le r_i \le 100\,000
1440\,0001\,000
1550\,00015\,000
16100\,00020\,000
17200\,0000 \le l_i \le r_i \le 10^9
18300\,00050\,000
19400\,00090\,000
20500\,000200\,000

Comments

There are no comments at the moment.