1044 - Task Arrangement I

Time Limit: 1s Memory Limit: 64MB

Submissions: 97 Solved: 33
Description
There are N tasks, and every task is asked to use the same resource. Every task i has a start time Si and a finish time Fi, so the task i use the resource during the time period [Si, Fi). But at the same time, there are at most M tasks can use the same resource. You are asked to find the best arrangement to maximum the total number of the compatible tasks.
Input
There are multi test cases. Each case contains a number of lines. The first line is N and M, 1 <= N <= 10000, 1 <= M <= 100. The next N lines, every line has two integers S and F, 0 <= S < F <= 100000000.
Output
For each test case, output one line containing the maximum number of the compatible tasks.
Sample Input
5 2
29 53
21 41
34 72
41 73
15 36
10 3
11 30
17 47
32 63
12 36
17 53
29 32
22 31
19 37
43 50
11 54
Sample Output
3
5
Hint
Source
Du Peng