Any ideas please share and appreciate that.

Interview question, hope to help.

Choose from a list of intervals, to make full coverage of target interval with minimum selection. If cannot cover, return -1.

for example: [[3,6],[4,5],[7,10],[6,9],[7,12],[12,17],[10,13],[18,22],[16,18]]; target is [7, 22]; should return 3;

here is my solution, with O(n) time and O(n) space. The idea is similar to LeetCode 45. Jump Game II. The tricky part is how to find the starting point to just cover the target.start. Basically, it is a Greedy question. I used the "sweep line" like method to build an auxiliary array to mimic the Jump Game.

```
public class MinimumCoverInterval {
public int minimumCoverInterval(Interval[] intervals, Interval target) {
if (intervals == null || intervals.length == 0) return 0;
int min = Integer.MAX_VALUE;
int max = 0;
for (Interval i : intervals) {
min = Math.min(min, i.start);
max = Math.max(max, i.end);
}
int[] count = new int[max - min + 1];
for (Interval i : intervals) {
count[i.start - min] = Math.max(count[i.start - min], i.end - i.start);
}
int reach = 0;
int maxReach = 0;
int target_start = target.start - min;
int target_end = target.end - min;
int i = 0;
for (; i <= target_start; i++) {
if (i + count[i] < target_start) continue;
reach = Math.max(reach, i + count[i]);
}
int res = 1;
for (; i < count.length; i++) {
if (reach >= target_end) break;
maxReach = Math.max(maxReach, i + count[i]);
if (reach <= i) {
reach = maxReach;
res++;
}
}
return reach >= target_end ? res : -1;
}
}
```