JS solution; O(n * log(n)) time


  • 0
    Y
    export default function merge(intervals) {
      const merged = []
      if (!intervals.length) {
        return merged
      }
      // first sort all the intervals in ascending order according to midpoint
      intervals.sort((intervalA, intervalB) => intervalA.start - intervalB.start)
      for (const interval of intervals) {
        if (!merged.length) {
          merged.push([interval.start, interval.end])
          continue
        }
        const [lastStart, lastEnd] = merged[merged.length - 1]
        const {start, end} = interval
        if (
          (lastStart <= start && start < lastEnd) ||
          (lastEnd === start)
        ) {
          merged[merged.length - 1][1] = Math.max(end, lastEnd)
        } else {
          merged.push([start, end])
        }
      }
      return merged
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.