Cutting Intervals
Memory limit1024 MB
Given N intervals and at most C integer cuts, choose cut points so the total number of resulting intervals is maximized; each cut at X splits every interval that strictly contains X.
- Level
Medium7 of 10
- Topics
- Greedy, Sorting, Intervals, Prefix sum
- Solved
- No attempts yet
Problem
You are given N intervals. An interval can be represented by two positive integers Li and Ri: it starts at Li and ends at Ri, written as [Li,Ri]. Intervals may not be unique, so there might be multiple intervals with both equal Li and equal Ri.
You are allowed to perform at most C cuts. A cut at X cuts all intervals [L,R] for which L<X and X<R. Cutting an interval at X splits the interval into two intervals, [L,X] and [X,R]. Cuts can only be performed at integer points. Also, cutting at an endpoint of an interval (X=L or X=R) has no effect and does not split the interval.
Find the maximum number of intervals that can be obtained with at most C cuts.
Input
The first line of the input contains the number of test cases, T. T test cases follow.
Each test case starts with a line containing two integers, N and C, the number of intervals and the maximum number of cuts you can perform. N lines follow.
The i-th line contains two integers Li and Ri, describing the i-th interval.
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of intervals that can be obtained with at most C cuts, as described above.
Constraints
- 1 ≤ T ≤ 100.
Hint
In the provided sample, cuts should be performed at 2 and 3 to get the maximum number of intervals.
After the first cut at 2, the intervals would be {[1,2],[2,3],[2,4],[1,2],[2,4]}.
After the second cut at 3, the intervals would be {[1,2],[2,3],[2,3],[3,4],[1,2],[2,3],[3,4]}.
No interval can be cut further, so the answer is 7.