시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
서브태스크 참고 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 21 | 18 | 16 | 88.889% |
You are given N intervals. An interval can be represented by two positive integers Li and Ri - the interval starts at Li and ends at Ri, represented 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 a maximum of C cuts. A cut at X will cut all intervals [L,R] for which L<X and X<R. Cutting an interval at X is defined as splitting the interval into two intervals - [L,X] and [X,R]. Note that 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.
You need to find the maximum number of intervals that can be obtained through a maximum of C cuts.
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, denoting the number of intervals and the maximum number of cuts you can perform respectively. N lines follow.
The i-th line contains two integers Li and Ri, describing the i-th interval.
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 through at most C cuts, as described above.
시간 제한: 20 초
시간 제한: 40 초
1 3 3 1 3 2 4 1 4
Case #1: 7
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]}.
It can be seen that no interval can be cut further, so the answer is 7.
Contest > Google > Kick Start > Google Kick Start 2021 > Round D B번