package com.freetymekiyan.algorithms.other;

import com.freetymekiyan.algorithms.utils.Utils.Interval;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

/**
 * Given a list of intervals, List<Interval> intervals, and a target interval, target. Merge these intervals and try to
 * cover target. Find the minimum number of intervals needed.
 * <p>
 * Example:
 * intervals: [[-1, 9], [1, 10], [0, 3], [9, 10], [3, 14], [2, 9], [10, 16]]
 * target: [2, 15]
 * output: 2
 * Explanation: We may cover [2, 15] with [1, 10] and [10, 16], which is only 2 intervals.
 * <p>
 * Company: Facebook
 */
public class MergeIntervalsToCoverTarget {

    /**
     * Greedy.
     * Go through intervals and keep only overlapping ones.
     * | If none, return 0.
     * Sort the overlapping intervals first.
     * For each overlapping interval i:
     * | If i.start <= target.start and i.end > target.start, there is an overlap
     * |   record the end index to find the max.
     * |   The greedy idea here means every time we try to cover target as much as possible with maximum end.
     * Update target with maximum end index.
     * Now this iteration ends, we've covered target with 1 interval, so the count increments by 1.
     * At maximum we can merge all overlapping intervals, so count < overlap.size().
     */
    public int mergeToCover(List<Interval> intervals, Interval target) {
        List<Interval> overlaps = new ArrayList<>(intervals);
        // overlaps.removeIf(i -> i.end <= target.start || i.start >= target.end);
        for (Iterator<Interval> iter = overlaps.iterator(); iter.hasNext(); ) {
            Interval i = iter.next();
            if (i.end <= target.start || i.start >= target.end) {
                iter.remove();
            }
        }
        if (overlaps.isEmpty()) return 0;

        overlaps.sort(Comparator.comparingInt(i -> i.start));
        int count = 0;
        while (count < overlaps.size() && target.start < target.end) {
            int maxEnd = Integer.MIN_VALUE;
            for (int i = count; i < overlaps.size(); i++) {
                if (overlaps.get(i).start <= target.start && overlaps.get(i).end > maxEnd) {
                    maxEnd = overlaps.get(i).end;
                }
            }
            target.start = maxEnd;
            count++;
        }
        return target.start >= target.end ? count : 0;
    }
}
@@ -835,16 +835,25 @@
 tervals 
+by start 
 first.%0A 
@@ -943,41 +943,45 @@
 d %3E 
-target.start, there is an overlap
+maxEnd, the interval can be expanded.
 %0A   
@@ -988,17 +988,17 @@
   * %7C   
-r
+R
 ecord th
@@ -1152,24 +1152,32 @@
 pdate target
+'s start
  with maximu
@@ -1181,22 +1181,16 @@
 imum end
- index
 .%0A     *
@@ -1243,16 +1243,23 @@
  with 1 
+merged 
 interval
@@ -1267,21 +1267,30 @@
  so the 
-count
+# of intervals
  increme
@@ -1320,20 +1320,16 @@
 imum we 
-can 
 merge al
@@ -1355,35 +1355,8 @@
 vals
-, so count %3C overlap.size()
 .%0A  
@@ -1754,32 +1754,69 @@
 %3E= target.end) %7B
+ // Remove non-overlapping intervals.
 %0A               
@@ -1972,21 +1972,30 @@
     int 
-count
+numOfIntervals
  = 0;%0A  
@@ -2007,21 +2007,30 @@
  while (
-count
+numOfIntervals
  %3C overl
@@ -2075,52 +2075,200 @@
 d) %7B
-%0A            int maxEnd = Integer.MIN_VALUE;
+ // Not all used and target hasn't been covered.%0A            // Build a merged interval to cover target.%0A            int maxEnd = Integer.MIN_VALUE; // Max end current intervals can expand to.
 %0A   
@@ -2289,21 +2289,30 @@
 int i = 
-count
+numOfIntervals
 ; i %3C ov
@@ -2546,94 +2546,253 @@
 End;
-%0A            count++;%0A        %7D%0A        return target.start %3E= target.end ? count : 0;
+ // maxEnd might make start even smaller. But it'll still exit when all intervals are used.%0A            numOfIntervals++;%0A        %7D%0A        return target.start %3E= target.end ? numOfIntervals : 0; // Check whether target is covered before return.
 %0A   

update Merge Intervals To Cover Target