解析 56. Merge Intervals # approach 1 - elegent way (neetcode) # - time: O(nlogn) # - space: O(1) def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key=lambda pair: pair[0]) res = [intervals[0]] for i in range(1, len(intervals)): interval = intervals[i] lastEnd = res[-1][1] if lastEnd >= interval[0]: # has overlap between the current interval and the previous added interval res[-1][1] = max(lastEnd, interval[1]) # merge else: # not has overlap
...
[Notes] Binary Heap
Knowledge
Refer to https://swsmile.info/post/data-structure-heap/
堆化（heapifying）
def heapify(arr, n, i):
"""
Function to heapify a subtree rooted with node i which is an index in arr[]. n is size of heap
"""
largest = i # Initialize largest as root
left = 2 * i + 1 # left = 2*i + 1
right = 2 * i + 2 # right = 2*i + 2
# See if left child of root exists and is greater than root
if left < n and arr[left] > arr[largest]:
largest = left
# See if right child of root exists and is greater than the root
if right < n and arr[right] > arr[largest]:
largest = right
# Change root, if needed
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # swap
# Heapify the root
heapify(arr, n, largest)
# Example usage
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
# Build a maxheap
for i in range(n//2 - 1, -1, -1):
heapify(arr, n, i)
