56. Merge Intervals

https://leetcode.com/problems/merge-intervals/

solution

• 根据起点或终点排序, 根据上一个终点和这一个起点的关系判断有无overlap

• 注意循环的控制方式，尤其是用输入list和输出list进行比较

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:

        intervals = sorted(intervals, key=lambda x: x[0])
        res = []

        for i in intervals:
            if res and i[0] <= res[-1][1]:
                res[-1][1] = max(i[1], res[-1][1])
            else:
                res.append(i)
        return res

时间复杂度：O(nlogn) 空间复杂度：O(n)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        res = [intervals[0]]
        for i in range(1, len(intervals)):
            if intervals[i][0] <= res[-1][1]:
                res[-1][1] = max(res[-1][1], intervals[i][1])
            else:
                res.append(intervals[i])
        return res

follow up - 间隔类题目

57. Insert Interval

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        i = 0
        n = len(intervals)
        res = []
        while i < n and intervals[i][1] < newInterval[0]:
            res.append(intervals[i])
            i += 1

        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(intervals[i][0], newInterval[0])
            newInterval[1] = max(intervals[i][1], newInterval[1])
            i += 1

        res.append(newInterval)

        while i < len(intervals):
            res.append(intervals[i])
            i += 1
        return res

435. Non-overlapping Intervals

• 和上题思路一样，排序后如果发现有重叠，那么按照贪心把重叠中更长的项删除

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key=lambda x: x[0])

        res = []
        for i in intervals:
            if res and i[0] < res[-1][1]:
                if i[1] > res[-1][1]:
                    pass
                else:
                    res.pop(-1)
                    res.append(i)
            else:
                res.append(i)
        return len(intervals) - len(res)

时间复杂度：O() 空间复杂度：O()

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0

        intervals.sort(key=lambda x: x[0])
        res = 1
        for i in range(1, len(intervals)):
            if intervals[i][0] >= intervals[i-1][1]:
                res += 1
            else:
                intervals[i][1] = min(intervals[i][1], intervals[i-1][1])

        return len(intervals) - res

时间复杂度：O() 空间复杂度：O()

*252. Meeting Rooms

class Solution:
    def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
        intervals.sort()
    
        for i in range(1, len(intervals)):
            if intervals[i - 1][1] > intervals[i][0]:
                return False    
        return True

时间复杂度：O() 空间复杂度：O()

1288. Remove Covered Intervals

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0

        intervals.sort(key=lambda x: (x[0], -x[1]))
        res = []
        for interval in intervals:
            if res and (interval[0] >= res[-1][0] and interval[1] <= res[-1][1]):
                continue
            res.append(interval)
        return len(res)

时间复杂度：O(sort) 空间复杂度：O(1)

*253. Meeting Rooms II

759 Employee Free Time

452. Minimum Number of Arrows to Burst Balloons

1094. Car Pooling

# 相比nested loop，优化了复杂度
class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        path = [0] * (max([i[2] for i in trips]) + 1)
        for a, s, e in trips:
            path[s] += a
            path[e] -= a
        res = 0
        for n in path:
            res += n
            if res > capacity:
                return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        heap = []
        for numPassengers, start, end in trips:
            heap.extend([(start, numPassengers), (end, -numPassengers)])
        heapify(heap)

        while capacity >= 0 and heap:
            capacity -= heappop(heap)[1]

        return len(heap) == 0

986. Interval List Intersections

# https://leetcode.com/discuss/interview-question/124616/

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        i = 0
        j = 0

        res = []
        while i < len(firstList) and j < len(secondList):
            l1 = firstList[i]
            l2 = secondList[j]

            if l1[1] >= l2[0] and l1[0] <= l2[1]:  # 注意此处的判断两个interval有相交的条件
                res.append([max(l1[0], l2[0]), min(l1[1], l2[1])])

            if l1[1] < l2[1]:
                i += 1
            else:
                j += 1
        return res

时间复杂度：O(n) 空间复杂度：O(n)

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        i = 0
        j = 0
        res = []

        while i < len(firstList) and j < len(secondList):
            if firstList[i][1] < secondList[j][0]:
                i += 1
            elif secondList[j][1] < firstList[i][0]:
                j += 1
            else:
                res.append([max(firstList[i][0], secondList[j][0]), min(firstList[i][1], secondList[j][1])])
                if firstList[i][1] < secondList[j][1]:
                    i += 1
                else:
                    j += 1
        return res