[LeetCode] 56. Merge Intervals(合并区间)

Description

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.
给定一组区间 intervalsintervals[i] = [starti, endi]),合并所有重叠的区间,并返回一个没有重叠的区间,这个区间能正好覆盖输入的区间。

Examples

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

首先,有序的区间方便于合并,所以第一步自然是给区间排序。然后取出第一个区间并遍历剩余区间:

  • 如果 end 大于等于遍历到的区间的 start,更新 end;

  • 否则,将这个区间加入结果集,更新当前的区间。

代码如下:

import kotlin.math.max

class Solution {
    fun merge(intervals: Array<IntArray>): Array<IntArray> {
        intervals.sortWith(Comparator { i1, i2 ->
            if (i1[0] != i2[0]) {
                compareValues(i1[0], i2[0])
            } else {
                compareValues(i1[1], i2[1])
            }
        })
        if (intervals.isEmpty()) {
            return arrayOf()
        }
        val result = arrayListOf<IntArray>()
        var (start, end) = intervals[0]
        for (i in 1..intervals.lastIndex) {
            if (end >= intervals[i][0]) {
                end = max(end, intervals[i][1])
            } else {
                result.add(intArrayOf(start, end))
                start = intervals[i][0]
                end = intervals[i][1]
            }
        }
        result.add(intArrayOf(start, end))
        return result.toTypedArray()
    }
}
上一篇:LeetCode题解(1681):最小不兼容性(Python)


下一篇:基于单片机的4*4*4光立方取模软件及相应的源码