LeetCode-in-All

56. Merge Intervals

Medium

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[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: intervals = [[1,4],[4,5]]

Output: [[1,5]]

Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

Solution

object Solution {
    def merge(intervals: Array[Array[Int]]): Array[Array[Int]] = {
        // Sort intervals based on the start values.
        val sortedIntervals = intervals.sortBy(_(0))
        val list = new collection.mutable.ListBuffer[Array[Int]]
        var current = sortedIntervals(0)
        list += current

        for (i <- 1 until sortedIntervals.length) {
            val next = sortedIntervals(i)
            if (current(1) >= next(0)) {
                // Merge overlapping intervals by updating the end value.
                current(1) = math.max(current(1), next(1))
            } else {
                current = next
                list += current
            }
        }

        list.toArray
    }
}

This site is open source. Improve this page.