LeetCode 57. 插入区间（难）

贪心算法，更简洁，不需要寻找插入位置，算法复杂度更低。如果输入数据本身有序，则我们不需要进行排序，那么该贪心算法具有 \(\mathcal{O}(N)\) 的时间复杂度。

题目

给出一个无重叠的，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例

示例 1:

1 2	`输入: intervals = [[1,3],[6,9]], newInterval = [2,5] 输出: [[1,5],[6,9]]`

示例 2:

1 2	`输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] 输出: [[1,2],[3,10],[12,16]]`

解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

考察知识点

排序、数组

核心思想

方法一、二分查找加上区间合并

承接 56. 合并区间（中）的思路，先找到应该插入的位置，然后把区间插进去，最后再合并。

算法

找到要插入的位置，将待插入的区间插入区间数组。
- 三种特殊情况，intervals为空，插入位置在第一位，插入位置在最后一位。
- 非特殊情况，使用二分查找确定插入位置。
使用LeetCode 56题的思路合并区间。

方法二、贪心算法

推荐该方法，更简洁，不需要寻找插入位置，算法复杂度更低。

贪心算法一般用来解决需要 “找到要做某事的最小数量” 或 “找到在某些情况下适合的最大物品数量” 的问题，且提供的是无序的输入，在输入为无序时，优势很明显。贪心算法的思想是每一步都选择最佳解决方案，最终获得全局最佳的解决方案。

标准解决方案具有 \(\mathcal{O}(N \log N)\) 的时间复杂度且由以下两部分组成：思考如何排序输入数据（\(\mathcal{O}(N \log N)\) 的时间复杂度）。思考如何解析排序后的数据（\(\mathcal{O}(N)\) 的时间复杂度）

如果输入数据本身有序，则我们不需要进行排序，那么该贪心算法具有 \(\mathcal{O}(N)\) 的时间复杂度。如何证明你的贪心思想具有全局最优的效果：可以使用反证法来证明。

让我们来看下面的例子来理解：

我们可以分为三个步骤去实现它：

在区间 newInterval 之前开始的区间全部添加到输出中。

将 newInterval 添加到输出中，如果与输出中的最后一个区间重合则合并它们。

然后一个个添加后续的区间，如果重合则合并它们。

算法

初始化 new_start, new_end, idx, n, output，分别代表待插入区的开始、结尾、遍历下标、区间数组长度、输出变量保存位置。
将 newInterval 之前开始的区间添加到输出，while idx < n and new_start > intervals[idx][0]。
添加 newInterval 到输出，若 newInterval 与输出中的最后一个区间重合则合并他们。通过判断当前output 最后一个区间的 end 是否小于 new_start 来决定是否重合。注意这里要注意判断`output 为空的情况， not output 。
- 没有重合，直接添加到 output 中。
- 有重合，进行合并，修改 output[-1][1] 即可。
一个个添加区间到输出，若有重叠部分则合并他们。
- 获取当前区间的 start, end 。
- 还是通过判断当前 output 最后一个区间的 end 是否小于 new_start 来决定是否重合。
  - 没有重合，直接添加到 output 中。
  - 有重合，进行合并。

LeetCode官方题解

Python版本

方法一实现

class Solution:
    def binary_search(self, nums, target):
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = (left + ((right - left) // 2))
            if nums[mid] == target:
                left = mid
                break
            if nums[left] < target < nums[right] and (right-left) == 1:
                break
            if nums[mid] < target:  # 去右边的区间找，增大左侧指针。
                left = mid
            else:  # 去左边的区间找，减小右侧指针。
                right = mid

        return left

    def traverse_search(self, nums, target):
        for i in range(len(nums)):
            if i + 1 < len(nums) and nums[i] <= target <= nums[i + 1]:
                return i

    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        # 使用二分查找，找到要插入的位置。
        target = newInterval[0]
        # 三种特殊情况，intervals为空，插入位置在第一位，插入位置在最后一位。
        if len(intervals) == 0:
            intervals = [newInterval]
            return intervals
        else:
            if newInterval[0] >= intervals[-1][0]:  # 插在后面
                intervals = intervals[:] + [newInterval]
            elif newInterval[0] <= intervals[0][0]:  # 插在前面
                intervals = [newInterval] + intervals[:]
            else:
                # 确定插入位置
                interval_indexs = [x[0] for x in intervals]
                # 可以通过遍历确定插入位置
                # left = self.traverse_search(interval_indexs, target)
                # 也可以通过二分查找确定插入位置
                left = self.binary_search(interval_indexs, target)
                # 将new Interval插入到intervals
                front_intervals = intervals[:left + 1]
                back_intervals = intervals[left + 1:]
                intervals = front_intervals[:] + [newInterval] + back_intervals[:]

        # 合并区间
        reslut = []
        for interval in intervals:
            if len(reslut) == 0 or reslut[-1][1] < interval[0]:
                reslut.append(interval)
            else:
                reslut[-1][1] = max(interval[1], reslut[-1][1])
        
        return reslut

print("leet code accept!!!")
Input = [[[0,2],[3,6],[7,7],[8,13],[14,21]], [[2,3],[5,5],[6,6],[7,7],[8,11]], [], [[2,5]], [[1,5]], [[1,2],[3,5],[6,7],[8,10],[12,16]], [[1,3],[6,9]]]
Input1 = [[13,21], [6,13], [5,7], [1,6], [2,3], [4,8], [2,5]]
Answer = [[[0, 2], [3, 6], [7, 7], [8, 21]], [[2, 3], [5, 5], [6, 13]], [[5,7]], [[1,6]], [[1,5]], [[1,2],[3,10],[12,16]], [[1,5],[6,9]]]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.insert(Input[i], Input1[i])
        print(reslut == Answer[i])

时间复杂度：\(O(n\ log\ n)\) ，\(n\) 是输入区间数组的长度。
空间复杂度：\(O(2 \times m)\) ，\(m\) 是最终结果数组的长度。

使用循环遍历方法寻找插入位置的结果
执行用时 :44 ms, 在所有 Python3 提交中击败了94.81%的用户
内存消耗 :14.9 MB, 在所有 Python3 提交中击败了100.00%的用户

使用二分查找方法寻找插入位置的结果
执行用时 :36 ms, 在所有 Python3 提交中击败了98.94%的用户
内存消耗 :15.1 MB, 在所有 Python3 提交中击败了100.00%的用户

方法二的实现

class Solution:
    def insert(self, intervals: 'List[Interval]', newInterval: 'Interval') -> 'List[Interval]':
        # init data
        new_start, new_end = newInterval
        idx, n = 0, len(intervals)
        output = []
        
        # add all intervals starting before newInterval
        # 在区间 newInterval 之前开始的区间全部添加到输出中。
        while idx < n and new_start > intervals[idx][0]:
            output.append(intervals[idx])
            idx += 1

        # 将 newInterval 添加到输出中，如果与输出中的最后一个区间重合则合并它们。
        if not output or output[-1][1] < new_start:  # 通过判断当前output最后一个区间的end是否小于new_start来决定是否重合。
            output.append(newInterval)  # 没有重合，直接添加。
        # if there is an overlap, merge with the last interval
        else:  # 有重合，进行合并。
            output[-1][1] = max(output[-1][1], new_end)
        
        # add next intervals, merge with newInterval if needed
        # 然后一个个添加后续的区间，如果重合则合并它们。
        while idx < n:
            interval = intervals[idx]
            start, end = interval
            idx += 1
            # if there is no overlap, just add an interval
            if output[-1][1] < start:  # 没有重合，直接添加。
                output.append(interval)
            # if there is an overlap, merge with the last interval
            else:  # 有重合，进行合并。
                output[-1][1] = max(output[-1][1], end)
        return output

时间复杂度：\(\mathcal{O}(N)\)。我们只遍历了一次输入元素。
空间复杂度：\(\mathcal{O}(N)\)，输出答案所使用的空间。
执行用时 :60 ms, 在所有 Python3 提交中击败了85.78%的用户
内存消耗 :15 MB, 在所有 Python3 提交中击败了100.00%的用户

有效语法糖

1、Python的list对象的插入操作

#!/usr/bin/python

aList = [123, 'xyz', 'zara', 'abc']
aList.insert( 3, 2009)
print "Final List : ", aList

Final List : [123, 'xyz', 'zara', 2009, 'abc']

LeetCode

贪心算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LeetCode 58. 最后一个单词的长度（易）上一篇

LeetCode 56. 合并区间（中）下一篇