package com.freetymekiyan.algorithms.level.medium;

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

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

/**
 * 56. Merge Intervals
 * <p>
 * Given a collection of intervals, merge all overlapping intervals.
 * <p>
 * For example,
 * Given [1,3],[2,6],[8,10],[15,18],
 * return [1,6],[8,10],[15,18].
 * <p>
 * Company Tags: LinkedIn, Google, Facebook, Twitter, Microsoft, Bloomberg, Yelp
 * Tags: Array, Sort
 * Similar Problems: (H) Insert Interval, (E) Meeting Rooms, (M) Meeting Rooms II
 */
public class MergeIntervals {


    /**
     * Sort. Greedy. O(nlogn) Time.
     * Sort the intervals by start time, ascending.
     * Use a pointer, prev, for previous merged interval.
     * For each of the intervals:
     * | If prev == null, merged is empty, add directly and update prev.
     * | If prev.end < i.start, no overlap, add directly and update prev.
     * | Else if prev.end >= i.start, there is overlap.
     * |   We already know i.start >= prev.start because of sorting. No need to update start.
     * |   Only update end is enough.
     * |   If prev.end >= i.end, no need to update end.
     * |   If prev.end < i.end, update end to i.end.
     */
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() <= 1) {
            return intervals;
        }
        List<Interval> merged = new ArrayList<>();
        Collections.sort(intervals, (i1, i2) -> Integer.compare(i1.start, i2.start));
        Interval prev = null; // A pointer to the last interval in merged list.
        for (Interval i : intervals) {
            if (prev == null || prev.end < i.start) { // Empty list or no overlap.
                merged.add(i);
                prev = i; // Update previous pointer.
            } else if (prev.end < i.end) { // Overlap and the end of current interval is larger.
                prev.end = i.end; // Update previous end to merge.
            }
        }
        return merged;
    }

    /**
     * Sort. Greedy. In-place.
     * Practically this implement is slower because for each loop runs faster.
     */
    public List<Interval> merge2(List<Interval> intervals) {
        intervals.sort(Comparator.comparingInt(i -> i.start));
        for (int i = 1; i < intervals.size(); i++) {
            Interval prev = intervals.get(i - 1);
            Interval current = intervals.get(i);
            if (prev.end < current.start) continue;
            prev.end = current.end > prev.end ? current.end : prev.end;
            intervals.remove(i);
            i--;
        }
        return intervals;
    }
}
@@ -125,99 +125,9 @@
 til.
-ArrayList;%0Aimport java.util.Collections;%0Aimport java.util.Comparator;%0Aimport java.util.List
+*
 ;%0A%0A/
@@ -2605,9 +2605,1014 @@
 ;%0A    %7D%0A
+%0A    /**%0A     * Sort.%0A     * Sort starts and ends of all intervals separately.%0A     * Compare start%5Bi+1%5D with end%5Bi%5D.%0A     * Use j to track next start to be added.%0A     * If start%5Bi+1%5D %3E end%5Bi%5D, no overlap, add start%5Bj%5D and end%5Bi%5D as an interval.%0A     * Update j with i+1, which is the next start after start%5Bi%5D and end%5Bi%5D.%0A     */%0A    public List%3CInterval%3E merge3(List%3CInterval%3E intervals) %7B%0A        int n = intervals.size();%0A        int%5B%5D starts = new int%5Bn%5D;%0A        int%5B%5D ends = new int%5Bn%5D;%0A        for (int i = 0; i %3C n; i++) %7B%0A            starts%5Bi%5D = intervals.get(i).start;%0A            ends%5Bi%5D = intervals.get(i).end;%0A        %7D%0A        Arrays.sort(starts);%0A        Arrays.sort(ends);%0A        List%3CInterval%3E res = new ArrayList%3C%3E();%0A        for (int i = 0, j = 0; i %3C n; i++) %7B // j is start of interval.%0A            if (i == n - 1 %7C%7C starts%5Bi + 1%5D %3E ends%5Bi%5D) %7B%0A                res.add(new Interval(starts%5Bj%5D, ends%5Bi%5D));%0A                j = i + 1;%0A            %7D%0A        %7D%0A        return res;%0A    %7D%0A%0A
 %7D

add 3rd solution to 56. Merge Intervals