这道题就是区间插入问题,目前看到的解法主要有三种,一种是直接分析区间重叠,具有O(n)时间和O(n)空间复杂度,另一种是用二叉搜索树来做,还有一种是借助了STL库中的equal_range方法来做,写法比较优雅。这篇博客主要给出第一种解法和第三种解法的代码

题目

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

分析区间重叠

博主的解是分析区间重叠的,速度是16ms。四个if的意思是,

  1. 如果该原区间与插入区间不重叠,则将原区间保留
  2. 中间两个for循环:如果该原区间与插入区间部分重叠,则将插入区间拓展,并删除原对应区间
  3. 如果原区间包含了插入区间,则直接返回(因为插入和没插入效果一样)

最后要按照顺序把区间摆好,如果没有约定拜访顺序的话,输入也是要做检查的。

借助STL库equal_range

推荐的优雅的答案,速度12ms,核心还是equal_range方法的使用

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注