# **程式筆記(Intervals)**

:::info
:information_source: 日期 : 2023/07/25
:::

**:thumbsup:** 通則

intervals四點
1. 要.sort()
2. 不管有沒有overlap都要更新preEnd
3. 要看"剛好overlap"這點的條件
4. 改end要用res[-1][1]

有重疊
if 舊(x)尾 >= 新進(x + 1)頭

list.sort() 直接修改原始list
sorted() 不影響原始list

# 使用 list.sort()
my_list = [3, 1, 4]
my_list.sort()
print(my_list)  # Output: [1, 3, 4]

# 使用 sorted()
my_list = [3, 1, 4]
sorted_list = sorted(my_list)
print(sorted_list)  # Output: [1, 3, 4]
print(my_list)      # Output: [3, 1, 4]

lambda

# 小到大 根據第一個element排序
intervals.sort(key=lambda x: x[0])
# 倒敘 大到小
intervals.sort(key=lambda x: x[0], reverse=True)

# 根據多個值去排序
intervals.sort(key=lambda x: (x[0], x[1]))

# 不改變原始列表
sorted_intervals = sorted(intervals, key=lambda x: x[0])

---

**:thumbsup:題解**

**Intervals**

* Merge Intervals(合併區間)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x:x[0])
        res = [intervals[0]]

        for start, end in intervals[1:]:
            if start <= res[-1][1]:
                res[-1][1] = max(res[-1][1], end)   
            else:
                res.append([start, end])

        return res

* Non-overlapping Intervals(非重疊區間)
minimum number of intervals you need to remove to make the rest of the intervals non-overlapping

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda x : x[0])
        preEnd = intervals[0][1]
        res = 0

        for start, end in intervals[1:]:
            if start < preEnd:
                preEnd = min(preEnd, end)
                res += 1
            else:
                preEnd = end
        
        return res

* Insert Interval(插入區間)
三種情況

1. if not overlap : interval[1] < new[0] # interval __ new
    res.append(interval)
2. if not overlap : new[1] < interval[0] # new __ interval
    res.append(new)
    return res + interval[i:] # never overlap anymore
3. if overlap:
    new[0] = min(interval[0], new[0])
    new[1] = max(interval[1], new[1])

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        for i, interval in enumerate(intervals):
            if interval[1] < newInterval[0]: # interval __ new
                res.append(interval)
            elif newInterval[1] < interval[0]: # new __ interval
                res.append(newInterval)
                return res + intervals[i:] # never overlap anymore
            else:
                newInterval[0] = min(interval[0], newInterval[0])
                newInterval[1] = max(interval[1], newInterval[1])

        res.append(newInterval)
        return res

* Interval List Intersections
保留住最大的那個區間，進下一輪比較。上面條件是and，最後一輪停在最大與次大，並且由最大勝出，即可終止

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

        while i < len(firstList) and j < len(secondList):
            s_i, e_i = firstList[i][0], firstList[i][1]
            s_j, e_j = secondList[j][0], secondList[j][1]

            s_max = max(s_i, s_j)
            e_min = min(e_i, e_j)

            if s_max <= e_min:
                intersection.append([s_max, e_min])
            
            if e_i < e_j:
                i += 1
            else:
                j += 1

        return intersection

**Meeting Rooms**

* Meeting Rooms
重疊 -> F / 不重疊 -> T

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        if not intervals:
            return True
        intervals.sort(key = lambda x : x[0])
        preEnd = intervals[0][1]

        for start, end in intervals[1:]:
            if preEnd > start:
                return False
            else:
                preEnd = end
        
        return True

* Meeting Rooms II
垂直向上看數線的最大重疊數量

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        res, rooms = 0, 0
        record = collections.defaultdict(int)
        for start, end in intervals:
            record[start] += 1
            record[end] -= 1
        
        keys = dict(sorted(record.items(), key = lambda item : item[0])).keys()

        for key in keys:
            rooms += record[key]
            res = max(res, rooms)
        
        return res

* Minimum Number of Arrows to Burst Balloons
先初始化一根劍，不停的更新尾端，當上次尾端和這次的開頭重疊，代表interval重疊可以一劍射穿，取最小的ending去更新
不用紀錄start，因為不會被拿進來比較
初始化1是因為第一個element

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points = sorted(points)
        count = 1
        # preStart = points[0][0]
        preEnd = points[0][1]
        for start, end in points:
            if start <= preEnd: # overlapped
                # preStart = max(preStart, start)
                preEnd = min(preEnd, end)
            else:
                count += 1
                # preStart = start
                preEnd = end

        return count

---

**講解連結**

Provided by.

###### tags: `arrays` `note` `code`