Task Arrangement I
Time Limit : 1 Second
Memory Limit : 64 MB
Submission: 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