Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given[1,3],[2,6],[8,10],[15,18],
return[1,6],[8,10],[15,18].

分析

  1. sort by ascending starting point
  2. if start2 is not bigger than end1, which means there is overlapping between two intervals, then we merge these two and update new end for this new merged interval

  3. otherwise, if start3 is bigger than end2, which means there is no overlapping between two intervals, then we directly add this latter interval into result

图解

代码

class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        // special case
        if (intervals.size() <= 1)return intervals;

        // Sort by ascending starting point 
        intervals.sort((o1,o2)->o1.start - o2.start);

        List<Interval> result = new LinkedList<Interval>();
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;

        for (Interval interval : intervals) {
            if (interval.start <= end) // Overlapping intervals, move the end if needed
                end = Math.max(end, interval.end);
            else {                     // Disjoint intervals, add the previous one and reset bounds
                result.add(new Interval(start, end));
                start = interval.start;
                end = interval.end;
            }
        }

        // Add the last interval
        result.add(new Interval(start, end));
        return result;
    }
}

results matching ""

    No results matching ""