56. Merge Intervals

Problem

https://leetcode.com/problems/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

• Sort by start. This will make sure the former one won't be a proper subset of the latter one. (Because former.start <= latter.start and former.start <= latter.end)
• So we just have to check the former.end and the latter.start to see if there is a overlap.

/**
 * 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
    }

    const sortedIntervals = intervals.sort((a, b) => { return a.start - b.start })
    const result = [sortedIntervals[0]]

    for (let i = 1; i < sortedIntervals.length; i += 1) {
        let res = result[result.length-1]
        let sor = sortedIntervals[i]

        if (sor.start <= res.end) {
            res.end = res.end > sor.end? res.end: sor.end
        } else {
            result.push(sor)
        }
    }

    return result
};