56. Merge Intervals

Problem:

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 considerred overlapping.

Solution:

Sort then merge.

/**
 * Definition for an interval.
 * function Interval(start, end) {
 *     this.start = start;
 *     this.end = end;
 * }
 */
/**
 * @param {Interval[]} intervals
 * @return {Interval[]}
 */
var merge = function(intervals) {
  if (intervals.length <= 1) { return intervals }
  intervals.sort((a, b) => (a.start - b.start) || (a.end - b.end))
  let last = new Interval(intervals[0].start, intervals[0].end)
  const result = [last]
  for (let i = 1; i < intervals.length; i++) {
    const { start, end } = intervals[i]
    if (start > last.end) {
      last = new Interval(start, end)
      result.push(last)
    } else if (end > last.end) {
      last.end = end
    }
  }
  return result
};

Template generated via Leetmark.