leetcode 56. 合并区间网站首页 其他

leetcode 56. 合并区间

dengjiayue 2024-08-22 12:01:03

简介leetcode 56. 合并区间

leetcode 56. 合并区间

题目描述

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2：

输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

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

解题思路

法1

方法1:排序

对区间起始位置进行排序
根据相邻两个区间是否能组合起来进行区间组合

条件:上一个区间的右极限大于等于下一个区间的左极限

即: n[i][1]>=n[i+1][0]?

循环遍历数组,记录返回结果

时间复杂度(O(nlogn))
空间复杂度(O(n))

执行结果

法1

func merge(intervals [][]int) [][]int {
 // 先按区间起始位置进行排序
 sort.Slice(intervals, func(i, j int) bool {
  return intervals[i][0] < intervals[j][0]
 })

 result := [][]int{}
 start := intervals[0][0]
 end := intervals[0][1]

 // 遍历区间数组，合并重叠区间
 for i := 1; i < len(intervals); i++ {
  interval := intervals[i]
  if interval[0] <= end {
   // 当前区间与前一个区间重叠，更新合并后的结束位置
   end = max(end, interval[1])
  } else {
   // 当前区间与前一个区间不重叠，将前一个合并后的区间加入结果数组
   result = append(result, []int{start, end})
   // 更新起始位置和结束位置为当前区间的起始位置和结束位置
   start = interval[0]
   end = interval[1]
  }
 }

 // 将最后一个合并后的区间加入结果数组
 result = append(result, []int{start, end})

 return result
}

func max(a, b int) int {
 if a > b {
  return a
 }
 return b
}