Minimum number of Intervals to cover the Target Interval

https://leetcode.com/discuss/interview-question/algorithms/124727/minimum-number-of-intervals-to-cover-the-target-interval-on-solution

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 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;
 }

Arrays.sort(list, new Comparator<Interval>(){
   public int compare(Interval a, Interval b) {
    if (a.start != b.start) {
     return a.start - b.start;
    }
    return a.end - b.end;
   }
  });
  
  int num = 0, i = 0, start = interval.start, end = -1;
  while (i < list.length) {
   if (list[i].end <= start) {
    i++;
   } else {
    if (list[i].start > start) break;
    while (i < list.length && list[i].start < start) {
     end = Math.max(end, list[i].end);
     i++;
    }
    if (start != end) {
     num++;
     start = end;
    }
   }
  }
  
  if (end < interval.end)
   return 0;
  return num;

https://robinliu.gitbooks.io/leetcode/content/Sweep_Line.html
you are given a set of closed intervals. Design an efficient algorithm for finding a minimum sized set of numbers that cover all the intervals

Greedy algorithm:
intuition: focus on extreme points. at the time we must have a point: when a line ends ==> sort based on right end.

vector<int> FindMinimumVisits(vector<Interval> intervals) {
  if (intervals.empty()) {
    return {};
  }

  // Sort intervals based on the right endpoints.
  sort(intervals.begin(), intervals.end(),
       [](const Interval& a, const Interval& b) -> bool {
         return a.right < b.right;
       });
  vector<int> visits;
  int last_visit_time = intervals.front().right;
  visits.emplace_back(last_visit_time);
  for (const Interval& interval : intervals) {
    if (interval.left > last_visit_time) {
      // The current right endpoint, last_visit_time, will not cover any more
      // intervals.
      last_visit_time = interval.right;
      visits.emplace_back(last_visit_time);
    }
  }
  return visits;
}