NOI '16 P4 - Interval - DMOJ: Modern 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]$ $[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} \leq x \leq 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 \leq m \leq 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

Copy

Sample Output 1

Copy

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 \leq l_{i} \leq r_{i} \leq 100$
2	$20$ $20$	$10$ $10$
3	$199$ $199$	$3$ $3$	$0 \le l_i \le r_i \le 100\,000$ $0 \leq l_{i} \leq r_{i} \leq 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 \leq l_{i} \leq r_{i} \leq 5 000$
8	$200$ $200$	$50$ $50$
9	$200$ $200$	$50$ $50$	$0 \le l_i \le r_i \le 10^9$ $0 \leq l_{i} \leq r_{i} \leq 10^{9}$
10	$1\,999$ $1 999$	$500$ $500$	$0 \le l_i \le r_i \le 5\,000$ $0 \leq l_{i} \leq r_{i} \leq 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 \leq l_{i} \leq r_{i} \leq 10^{9}$
13	$30\,000$ $30 000$	$2\,000$ $2 000$	$0 \le l_i \le r_i \le 100\,000$ $0 \leq l_{i} \leq r_{i} \leq 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 \leq l_{i} \leq r_{i} \leq 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$

Comments

There are no comments at the moment.