P1712 [NOI2016] Intervals

On the number line, there are $n$ closed intervals numbered from $1$ to $n$. The $i$-th closed interval is $[l_i, r_i]$. Now we need to choose $m$ intervals such that these $m$ intervals share at least one position. In other words, there exists an $x$ such that for every selected interval $[l_i, r_i]$, we have $l_i \leq x \leq r_i$. For a valid selection, its cost is the length of the longest selected interval minus the length of the shortest selected interval. The length of an interval $[l_i, r_i]$ is defined as $(r_i - l_i)$, i.e., the value of the right endpoint minus the value of the left endpoint. Find the minimum cost among all valid selections. If no valid selection exists, output $-1$.

The first line contains two integers, representing $n$ and $m$. From line $2$ to line $(n + 1)$, each line contains two integers representing an interval. On line $(i + 1)$, the integers $l_i, r_i$ denote the left and right endpoints of the $i$-th interval.

Output a single integer on one line representing the answer.

#### Explanation for Sample Input/Output 1  As shown, when $n = 6$, $m = 3$, the minimum-cost plan is to select the three intervals $[3, 5], [3, 4], [1, 4]$. They all contain position $4$, so the selection is valid. Among them, the longest interval is $[1, 4]$, and the shortest interval is $[3, 4]$, so the cost is $(4 - 1) - (4 - 3) = 2$. #### Constraints and Conventions ::cute-table{tuack} There are 20 test points in total. See the table below for details. | Test point ID | $ n= $ | $ m= $ | $ l_i, r_i $ | |:-:|:-:|:-:|:-:| | 1 | $ 20 $ | $ 9 $ | $ 0 \le l_i \le r_i \le 100 $ | | 2 | ^ | $ 10 $ | $ 0 \le l_i \le r_i \le 100 $ | | 3 | $ 199 $ | $ 3 $ | $ 0 \le l_i \le r_i \le 100000 $ | | 4 | $ 200 $ | ^ | ^ | | 5 | $ 1000 $ | $ 2 $ | ^ | | 6 | $ 2000 $ | ^ | ^ | | 7 | $ 199 $ | $ 60 $ | $ 0 \le l_i \le r_i \le 5000 $ | | 8 | $ 200 $ | $ 50 $ | ^ | | 9 | ^ | ^ | $ 0 \le l_i \le r_i \le 10^9 $ | | 10 | $ 1999 $ | $ 500 $ | $ 0 \le l_i \le r_i \le 5000 $ | | 11 | $ 2000 $ | $ 400 $ | ^ | | 12 | ^ | $ 500 $ | $ 0 \le l_i \le r_i \le 10^9 $ | | 13 | $ 30000 $ | $ 2000 $ | $ 0 \le l_i \le r_i \le 100000 $ | | 14 | $ 40000 $ | $ 1000 $ | ^ | | 15 | $ 50000 $ | $ 15000 $ | ^ | | 16 | $ 100000 $ | $ 20000 $ | ^ | | 17 | $ 200000 $ | ^ | $ 0 \le l_i \le r_i \le 10^9 $ | | 18 | $ 300000 $ | $ 50000 $ | ^ | | 19 | $ 400000 $ | $ 90000 $ | ^ | | 20 | $ 500000 $ | $ 200000 $ | ^ | For all test points, it is guaranteed that $1 \le m \le n$, $1 \le n \le 5 \times 10^5$, $1 \le m \le 2 \times 10^5$, $0 \le l_i \le r_i \le 10^9$. Translated by ChatGPT 5