56. Merge Intervals (Medium)

https://leetcode.com/problems/merge-intervals/

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Solutions

class Solution {
    class Range{
        int left;
        int right;

        Range(int left, int right) {
            this.left = left;
            this.right = right;
        }

        public void merge(Range r) {
            // I made a mistake as follows:
            // this.right = r.right;
            // Above statement turns out to be incorrect when comes across [[1,4],[2,3]]

            this.right = Math.max(right, r.right);
        }
    }

    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }

        // convert int[][] to List<Range>
        List<Range> ranges = new ArrayList<>();
        for (int[] interval : intervals) {
            ranges.add(new Range(interval[0], interval[1]));
        }

        // sort all the ranges
        Collections.sort(ranges, (o1, o2) -> {
            if (o1.left != o2.left) {
                return o1.left - o2.left;
            }

            return o1.right - o2.right;
        });

        // list to hold all the merged ranges
        List<Range> mr = new ArrayList<>();

        // [1,3],[2,4],[3,5]
        // [[1,1],[1,1],[1,1]]

        Range pre = ranges.get(0);

        for (int i = 1; i < ranges.size(); i++) {
            Range cur = ranges.get(i);

            // add previous range if current two ranges do not have intersections
            if (cur.left > pre.right) {
                mr.add(pre);
                pre = cur;
            }
            // if two have intersections, the previous range will merge current one
            else {
                pre.merge(cur);
            }
        }


        // do not forget to add the final merged range
        mr.add(pre);

        int[][] ans = new int[mr.size()][2];
        for (int i = 0; i < mr.size(); i++) {
            ans[i][0] = mr.get(i).left;
            ans[i][1] = mr.get(i).right;
        }

        return ans;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""