0057. Insert Interval.md

• 0057 - Insert Interval
• 难度：Medium
• 相关知识点：Array
• 题目链接：https://leetcode.com/problems/container-with-most-water/description/

Solution 1

> 如果没有交集，直接插入，
> 有交集合并，
> 全程只需判断有没有交集，没有交集的前面和后面内容不需要处理，直接插入

"""
interval                |  |
#1 newInterval1               |    |  
#2 newInterval2    | |
#3 newInterval2           |   |
"""

from typing import List

class Solution:
    def insert(self, intervals: List[List[int]], new_interval: List[int]) -> List[List[int]]:
        result = []
        i = 0
        n = len(intervals)

        # Add intervals that come before the new_interval
        while i < n and intervals[i][1] < new_interval[0]:
            result.append(intervals[i])
            i += 1

        # Merge overlapping intervals
        while i < n and intervals[i][0] <= new_interval[1]:
            new_interval[0] = min(new_interval[0], intervals[i][0])
            new_interval[1] = max(new_interval[1], intervals[i][1])
            i += 1

        result.append(new_interval)

        # Add intervals that come after the new_interval
        while i < n:
            result.append(intervals[i])
            i += 1

        return result

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:        
        res = []

        for i in range(len(intervals)):
            if newInterval[0] > intervals[i][1]: # 1 在插入区间的左侧且无交集 
                res.append(intervals[i])
            elif newInterval[1] < intervals[i][0]: # 2 在插入区间的右侧且无交集
                res.append(newInterval)
                return res + intervals[i:]
            else:  # 3 与插入区间有交集
                newInterval = [min(newInterval[0], intervals[i][0]),
                              max(newInterval[1], intervals[i][1])]
        res.append(newInterval)
        return res

placed作为标记符号

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        left, right = newInterval
        placed = False
        ans = list()
        for li, ri in intervals:
            if li > right:
                # 在插入区间的右侧且无交集
                if not placed:
                    ans.append([left, right])
                    placed = True
                ans.append([li, ri])
            elif ri < left:
                # 在插入区间的左侧且无交集
                ans.append([li, ri])
            else:
                # 与插入区间有交集，计算它们的并集
                left = min(left, li)
                right = max(right, ri)
        
        if not placed:
            ans.append([left, right])
        return ans

Solution2

将newInterval插入intervals，之后做法跟Leetcode56 方法相同, 有无效计算

1. 直接sort
2. heapq

import heapq
from typing import List

class Solution:
    def insert(self, intervals: List[List[int]], new_interval: List[int]) -> List[List[int]]:
        result = []
        heapq.heapify(result)

        for interval in intervals:
            heapq.heappush(result, interval)

        heapq.heappush(result, new_interval)

        merged = [heapq.heappop(result)]
        while result:
            current = heapq.heappop(result)
            if merged[-1][1] >= current[0]:
                merged[-1][1] = max(merged[-1][1], current[1])
            else:
                merged.append(current)

        return merged