56. Merge Intervals

三刷

16.29 %
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() == 0) return intervals;
        Collections.sort(intervals, Comparator.comparing(a -> a.start));
        // sort intervals by their start position
        List<Interval> result = new ArrayList<>();
        int i = 0;
        while (i < intervals.size()) {
            Interval curr = intervals.get(i);
            while (i + 1 < intervals.size()
                   && intervals.get(i + 1).start <= curr.end) {
                i++;
                curr.end = Math.max(curr.end, intervals.get(i).end);
            }
            result.add(curr);
            i++;
        }
        return result;
    }
}

二刷
Sort intervals by their start point
Iterate the sorted list
We always see a start point, choose it as a base interval, check if next interval can be merged in.
If next interval's start point is less or equal to current end point, then it can be merged
The new end point after merged should be the max between current end point and the new merged interval's end point
Time O(nlogn)

19.64 %
class Solution {
    // a.start         a.end
    //   b.start   b.end
    public List<Interval> merge(List<Interval> intervals) {
        Collections.sort(intervals, (a, b) -> {
            return a.start - b.start;
        });
        List<Interval> result = new ArrayList<>();
   
        Interval merge = null;
        for (Interval curr : intervals) {
            if (merge == null || curr.start > merge.end) {
                if (merge != null) {
                    result.add(merge);
                }
                merge = new Interval(curr.start, curr.end);
            } else {
                merge.end = Math.max(merge.end, curr.end);
            }
        }
        if (merge != null) {
            result.add(merge);
        }
        return result;
    }
}

Version #3
Since all start and end points are paired, looking from left to right, there are always less or equals count of end points than start points.
For an interval, we always have same count of start points and end points.
Time O(nlogn)
Space O(n)
100.00 %
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        // j            i-1    i
        // s   s    e    e     s   e    s    e
        List<Interval> result = new ArrayList<>();
        if (intervals == null || intervals.size() == 0) {
            return result;
        }
        int size = intervals.size();
        int[] starts = new int[size];
        int[] ends = new int[size];
        for (int i = 0; i < size; i++) {
            starts[i] = intervals.get(i).start;
            ends[i] = intervals.get(i).end;
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int j = 0;
        for (int i = 0; i < size; i++) {
            if (i != 0 && starts[i] > ends[i - 1]) {
                result.add(new Interval(starts[j], ends[i - 1]));
                j = i;
            }
        }
        result.add(new Interval(starts[j], ends[size - 1]));
        // 1  2     8   15
        //      3 6   10   18
        return result;
    }
}


一刷
Version #3 Sort start/end separately
没有特别理解，但是这种方法应该是最快的


Version #2 sort start & end points

Input:[[1,4],[4,5]]

Output:[[1,4],[4,5]]

Expected:[[1,5]]

这个bug就是没有考虑算法哥说的breaking tie的情况
对于end == start来说，应该把start排在前面end排在后面
写comparator的时候一开始有个Line 26: java.lang.IllegalArgumentException: Comparison method violates its general contract!
因为在比较boolean isStart的时候可能遇到了Your compare() method is not transitive的情况
所以把boolean 改成了0/1
44.93 % 
class Solution {
    class Node {
        int val;
        int isStart;
        public Node(int val, int isStart) {
            this.val = val;
            this.isStart = isStart;
        }
    }
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() == 0) return intervals;
        List<Node> nodes = new ArrayList<>();
        for (Interval in : intervals) {
            nodes.add(new Node(in.start, 0));
            nodes.add(new Node(in.end, 1));
        }
        nodes.sort(new Comparator<Node>() {
            @Override
            public int compare(Node n1, Node n2) {
                if (n1.val != n2.val) return n1.val - n2.val;
                // start is smaller than end
                return n1.isStart - n2.isStart;
            }
        });
        List<Interval> result = new ArrayList<>();
        int count = 0;
        Integer left = null, right = 0;
        for (Node n : nodes) {
            // Breaking tie
            if (n.isStart == 0) {
                if (left == null) left = n.val;
                count++;
            } else {
                right = right.max(right, n.val);
                count--;
            }
            if (count == 0) {
                result.add(new Interval(left, right));
                left = null;
                right = 0;
            }
        }
        return result;
    }
}



Version #1 sort start points

Input:[[1,4],[2,3]]

Output:[[1,3]]

Expected:[[1,4]]

一开始写的有点乱
借用了sliding window的思路以后就很容易了
因为我自己写的时候right 初始永远比left 大1，所以进入while 的条件是left < size，避免left是最后一个的时候进不去

上面的edge case没有想到就非常蠢了，因为interval可以直接被包含
所以merge的时候右边界不是简单地取right.end而是要在curr.end 和right.end之间取max
27.88 %
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() <= 0) return intervals;
        intervals.sort((i1, i2) -> i1.start - i2.start);
        List<Interval> result = new ArrayList<>();
        int index = 0;
        int size = intervals.size();
        int left = 0, right = 1;
        while (left < size) {
            Interval curr = intervals.get(left);
            while (right < size && curr.end >= intervals.get(right).start) {
                curr = new Interval(curr.start, Math.max(curr.end, intervals.get(right).end));
                right++;
            }
            result.add(curr);
            left = right;
            right++;
        }
 
        return result;
    }
}