算法题--插入区间

image.png

0. 链接

题目链接

1. 题目

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:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 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].

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

2. 思路1：先按照左端点找到合适插入位置+再从插入位置向右尝试合并区间

3. 代码

# coding:utf8
from typing import List


class Solution:
    def find_insert_idx(self,
                        intervals: List[List[int]],
                        newInterval: List[int],
                        i):
        l = 0
        r = len(intervals) - 1
        while l <= r:
            mid = (l + r) >> 1
            if intervals[mid][i] < newInterval[i]:
                l = mid + 1
            elif intervals[mid][i] > newInterval[i]:
                r = mid - 1
            else:
                l = mid + 1

        return l

    def insert(self, intervals: List[List[int]], newInterval: List[int]) \
            -> List[List[int]]:
        if len(intervals) == 0:
            intervals.append(newInterval)
            return intervals

        idx = self.find_insert_idx(intervals, newInterval, 0)
        intervals.insert(idx, newInterval)

        if idx == 0:
            idx += 1

        while True:
            if idx <= len(intervals) - 1 and intervals[idx][0] <= intervals[idx - 1][1]:
                intervals[idx - 1][1] = max(intervals[idx - 1][1], intervals[idx][1])
                intervals.pop(idx)
            elif idx < len(intervals) - 1 and intervals[idx + 1][0] <= intervals[idx][1]:
                intervals[idx + 1][0] = intervals[idx][0]
                intervals[idx + 1][1] = max(intervals[idx + 1][1], intervals[idx][1])
                intervals.pop(idx)
            else:
                break

        return intervals


solution = Solution()
print(solution.insert([[1, 3], [6, 9]], [2, 5]))
print(solution.insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))
print(solution.insert([[1, 3]], [0, 1]))
print(solution.insert([[1, 5]], [2, 3]))
print(solution.insert([[1, 5]], [0, 6]))
print(solution.insert([[0, 5], [9, 12]], [7, 16]))
print(solution.insert([], [0, 1]))

输出结果

[[1, 5], [6, 9]]
[[1, 2], [3, 10], [12, 16]]
[[0, 3]]
[[1, 5]]
[[0, 6]]
[[0, 5], [7, 16]]
[[0, 1]]

4. 结果

image.png

5. 思路2：两端分别找到插入位置+合并

1. 先根据左端点值找到插入位置，再根据右端点值找到插入位置
2. 合并两个位置之间的区间, 再跟左位置之左的区间和右位置之右的区间合并

寻找过程使用二分查找法

6. 代码:

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) \
            -> List[List[int]]:
        if not intervals:
            return [newInterval]

        start = newInterval[0]
        end = newInterval[1]
        left = 0
        right = len(intervals) - 1

        if intervals[right][1] < start:
            intervals.append(newInterval)
            return intervals

        while left <= right:
            mid = (left + right) >> 1
            if intervals[mid][1] < start:
                left = mid + 1
            elif end < intervals[mid][0]:
                right = mid - 1
            elif intervals[left][1] < start:
                left += 1
            elif intervals[right][0] > end:
                right -= 1
            else:
                start = min(intervals[left][0], start)
                end = max(intervals[right][1], end)
                break

        return intervals[:left] + [[start, end]] + intervals[right + 1:]


solution = Solution()
print(solution.insert([[1, 3], [6, 9]], [2, 5]))
print(solution.insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))
print(solution.insert([[1, 3]], [0, 1]))
print(solution.insert([[1, 5]], [2, 3]))
print(solution.insert([[1, 5]], [0, 6]))
print(solution.insert([[0, 5], [9, 12]], [7, 16]))
print(solution.insert([], [0, 1]))

输出结果为:

[[1, 5], [6, 9]]
[[1, 2], [3, 10], [12, 16]]
[[0, 3]]
[[1, 5]]
[[0, 6]]
[[0, 5], [7, 16]]
[[0, 1]]

7. 结果

image.png