56 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].

Solution)

First, we have to sort the given intervals based on the start index.

Then, we can update the result list by merging intervals step by step by comparing.

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    List<Interval> merge(List<Interval> intervals) {
      if (intervals.size() < 2) return intervals;
      else {
        intervals.sort(Comparator.comparing(i -> i.start));
        List<Interval> results = new ArrayList<>();
        for (Interval interval : intervals) {
          if (!results.isEmpty() && interval.start <= results.get(results.size()-1).end)
              results.get(results.size()-1).end = Math.max(results.get(results.size()-1).end, interval.end);
          else results.add(interval);
        }
        return results;
      }
    }
}