Interval - MarisaOJ: Marisa Online Judge

Interval

Time limit: 2000 ms
Memory limit: 512 MB
Given $n$ closed intervals $[l_1, r_1], [l_2, r_2], ..., [l_n, r_n]$, you need to choose $m$ intervals such that they have at least one common point. In other words, there exists a point $x$ such that for every chosen interval $[l_i, r_i]$, $l_i \leq x \leq r_i$. For a satisfying selection, the cost of the choice is defined as the difference between the length of the longest interval and the length of the shortest interval. The length of an interval $[l_i, r_i]$ is defined as $r_i - l_i$. Find the minimum cost possible, or if there is no valid selection, output `-1`. ### Input - The first line consists of two integers $n$ and $m$. - The next $n$ lines, each containing two integers $l_i$ and $r_i$. ### Output - Output a single integer, the answer to the problem. If there is no valid selection, output `-1`. ### Example Input: ``` 6 3 3 5 1 2 3 4 2 2 1 5 1 4 ``` Output: ``` 2 ``` Explanation: - Choose $3$ intervals $[3,5], [3,4], [1,4]$. ### Constraints
Test $n$ $m$ $l_i, r_i$
$1$ $20$ $9$ $0 \leq l_i \leq r_i \leq 100$
$2$ $10$
$3$ $199$ $3$ $0 \leq l_i \leq r_i \leq 100000$
$4$ $200$
$5$ $1000$ $2$
$6$ $2000$
$7$ $199$ $60$ $0 \leq l_i \leq r_i \leq 5000$
$8$ $200$ $50$
$9$ $0 \leq l_i \leq r_i \leq 10^9$
$10$ $1999$ $500$ $0 \leq l_i \leq r_i \leq 5000$
$11$ $2000$ $400$
$12$ $500$ $0 \leq l_i \leq r_i \leq 10^9$
$13$ $30000$ $2000$ $0 \leq l_i \leq r_i \leq 100000$
$14$ $40000$ $1000$
$15$ $50000$ $15000$
$16$ $100000$ $20000$
$17$ $200000$ $0 \leq l_i \leq r_i \leq 10^9$
$18$ $300000$ $50000$
$19$ $400000$ $90000$
$20$ $500000$ $200000$