算法经典题目:Insert Interval
题目
给定一组无重叠的时间区间,将一个新的时间区间插入到这些区间中(如果需要的话进行合并)。你可以假设这些时间区间最初是按照它们的开始时间排序好的。
示例1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
示例2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
解题思路
可以分 3 段处理,先添加原来的区间,即在给的 newInterval 之前的区间。然后添加 newInterval ,注意这⾥可能需要合并多个区间。最后把原来剩下的部分添加到最终结果中即可。
答案:
func insert(intervals []Interval, newInterval Interval) []Interval {res := make([]Interval, 0)if len(intervals) == 0 {res = append(res, newInterval)return res}curIndex := 0for curIndex < len(intervals) && intervals[curIndex].End < newInterval.Start
{res = append(res, intervals[curIndex])curIndex++}for curIndex < len(intervals) && intervals[curIndex].Start <=
newInterval.End {newInterval = Interval{Start: min(newInterval.Start,
intervals[curIndex].Start), End: max(newInterval.End,
intervals[curIndex].End)}curIndex++}res = append(res, newInterval)for curIndex < len(intervals) {res = append(res, intervals[curIndex])curIndex++}return res
}
🚀 获取更多详细资料可点击链接进群领取,谢谢支持👇
点击免费领取更多资料