Little Lumber Jack has a good reputation in his family. He is said to have never missed one class in school!
He is now in the final year, ready to graduate, and he has a big issue. His friend, who was usually providing him with sick leaves, messed up and gave him a lot more sick leaves than he needed. Some of them even overlap!
Lumber Jack is in trouble, he can't take the sick leaves to his teacher like this because he would get suspicious. Neither should there be sick leaves that don't cover any day he was absent in, nor ones that overlap. Help Jack find a minimal subset of the sick leaves that satisfy those requirements, in order to preserve his reputation.
Input
On the first line of the input there are 3 integer numbers, D, N and M, where D is the number of days in the school year, N represents the number of days skipped by Lumber Jack and M denotes the number of sick leaves he has.
On the second line of the file there will be N integer numbers, separated by space, representing the days skipped.
The next M lines contain one pair of integer numbers each, X and Y, denoting the start and end days of the leave.
Output
A single integer number, denoting the minimum number of sick leaves Jack has to take in order to cover all the days he skipped school.
It is guaranteed that a solution will exist.
Constraints
- 1 ≤ N ≤ D, X, Y, M ≤ 1000
Sample
| Input | Output |
|---|---|
| 9 4 6 2 4 5 8 1 3 2 3 3 4 2 5 5 6 7 8 | 2 |
Solution by Inelus Gabriel Robert
There are solutions of varied complexities. An O(N2) algorithm will build a graph and do a Breadth-First Search.
The O(N) solution uses a dynamic programming approach. Let dp[i] = the least number of sick leaves needed for days i, i+1, …, D, D+1.
Initialisation
- dp[i] = infinity, ∀ i ∈ [1, D]
- dp[D+1] = 0
Recurrence relation
- dp[i] = min(dp[i], dp[i+1]), provided that Lumber Jack did not skip the ith day.
- dp[i] = min(dp[i], dp[next] + 1), provided that we have a sick leave on interval [i, next).
The dp[] table can be computed from high indices to low.
Hence, we can build a graph with an edge (i) → (next+1) in linear time using linked lists (or STL vectors) and then apply the above recurrence relation.
The final complexity is O(N) both time and space.
Note that given the low score of the problem, we accept slightly worse complexity solutions, however exponential complexities are not acceptable.
