NOI '16 P4 - Interval - Olympiads Online Judge

NOI '16 P4 - Interval

View as PDF

Submit solution

All submissions

Best submissions

Points: 20 (partial)

Time limit: 3.0s

Memory limit: 256M

Problem type

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

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

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

Input Specification

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

In the following $n$ ~n~ lines, each line consists of two integers $l_i, r_i$ ~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

Sample Output 1

Explanation for Sample 1

When $n = 6$ ~n = 6~, $m = 3$ ~m = 3~, the optimal solution is to choose intervals $[3, 5], [3, 4], [1, 4]$ ~[3, 5], [3, 4], [1, 4]~. $4$ ~4~ is contained in all three intervals. The longest interval is $[1, 4]$ ~[1, 4]~ and the shortest interval is $[3, 4]$ ~[3, 4]~, so the cost should be $(4-1)-(4-3) = 2$ ~(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 case	$n =$ ~n =~	$m=$ ~m=~	$l_i, r_i$ ~l_i, r_i~
1	$20$ ~20~	$9$ ~9~	$0 \le l_i \le r_i \le 100$ ~0 \le l_i \le r_i \le 100~
2	$20$ ~20~	$10$ ~10~	$0 \le l_i \le r_i \le 100$ ~0 \le l_i \le r_i \le 100~
3	$199$ ~199~	$3$ ~3~	$0 \le l_i \le r_i \le 100\,000$ ~0 \le l_i \le r_i \le 100\,000~
4	$200$ ~200~	$3$ ~3~
5	$1\,000$ ~1\,000~	$2$ ~2~
6	$2\,000$ ~2\,000~	$2$ ~2~
7	$199$ ~199~	$60$ ~60~	$0 \le l_i \le r_i \le 5\,000$ ~0 \le l_i \le r_i \le 5\,000~
8	$200$ ~200~	$50$ ~50~
9	$200$ ~200~	$50$ ~50~	$0 \le l_i \le r_i \le 10^9$ ~0 \le l_i \le r_i \le 10^9~
10	$1\,999$ ~1\,999~	$500$ ~500~	$0 \le l_i \le r_i \le 5\,000$ ~0 \le l_i \le r_i \le 5\,000~
11	$2\,000$ ~2\,000~	$400$ ~400~
12	$2\,000$ ~2\,000~	$500$ ~500~	$0 \le l_i \le r_i \le 10^9$ ~0 \le l_i \le r_i \le 10^9~
13	$30\,000$ ~30\,000~	$2\,000$ ~2\,000~	$0 \le l_i \le r_i \le 100\,000$ ~0 \le l_i \le r_i \le 100\,000~
14	$40\,000$ ~40\,000~	$1\,000$ ~1\,000~
15	$50\,000$ ~50\,000~	$15\,000$ ~15\,000~
16	$100\,000$ ~100\,000~	$20\,000$ ~20\,000~
17	$200\,000$ ~200\,000~	$20\,000$ ~20\,000~	$0 \le l_i \le r_i \le 10^9$ ~0 \le l_i \le r_i \le 10^9~
18	$300\,000$ ~300\,000~	$50\,000$ ~50\,000~
19	$400\,000$ ~400\,000~	$90\,000$ ~90\,000~
20	$500\,000$ ~500\,000~	$200\,000$ ~200\,000~