TagSort

Merge Interval.png

# 56. Merge Intervals
# Given a collection of intervals, merge all overlapping intervals.
# Input: [[1,3],[2,6],[8,10],[15,18]]
# Output: [[1,6],[8,10],[15,18]]

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        out = []
        for i in sorted(intervals, key=lambda i: i[0]): #区间首元素排序
            if out and i[0] <= out[-1][1]:              #新区间有交叉？
                out[-1][1] = max(out[-1][1], i[1])      #交叉则区间融合
            else:
                out += i,                               #不交叉 区间纳入
        return out

Meeting Rooms II.png

# 253. Meeting Rooms II
# an array of meeting time intervals 
# consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), 
# find the minimum number of conference rooms required.

 # Very similar with what we do in real life. Whenever you want to start a meeting, 
 # you go and check if any empty room available (available > 0) and
 # if so take one of them ( available -=1 ). Otherwise,
 # you need to find a new room someplace else ( numRooms += 1 ).  
 # After you finish the meeting, the room becomes available again ( available += 1 ).
class Solution:  
    def minMeetingRooms(self, intervals):
        starts = sorted(i[0] for i in intervals)
        ends = sorted(i[1] for i in intervals)
        e = 0
        numRooms = available = 0
        for start in starts:
            while ends[e] <= start:
                available += 1      
                e += 1
            if available:
                available -= 1
            else:
                numRooms += 1
        return numRooms

KClosest Points to Origin.png

# 973. K Closest Points to Origin
# a list of points on the plane.  
# Find the K closest points to the origin (0, 0).

# Put the points into a PriorityQueue, 
# and the order is by their distance to origin descendingly;
# Whenever the size reaches K + 1, poll the farthest point out.

#                         模块heapq中一些重要的函数
#        函 数                                              描 述
#   heappush(heap, x)                                        将x压入堆中
#     heappop(heap)                                      从堆中弹出最小的元素
#     heapify(heap)                                           让列表具备堆特征
# heapreplace(heap, x)                            弹出最小的元素，并将x压入堆中
#   nlargest(n, iter)                                       返回iter中n个最大的元素
#     nsmallest(n, iter)                                   返回iter中n个最小的元素

class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        # Time: O(nlogn), space: O(n).
        return heapq.nsmallest(K, points, lambda p: p[0] * p[0] + p[1] * p[1])    
    
# We keep a min heap of size K.
# For each item, we insert an item to our heap.
# If inserting an item makes heap size larger than k, 
# then we immediately pop an item after inserting ( heappushpop ).

# Runtime:
# Inserting an item to a heap of size k take O(logK) time.
# And we do this for each item points.
# So runtime is O(N * logK) where N is the length of points.

# Space: O(K) for our heap.
    
import heapq
class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        heap = []
        for (x, y) in points:
            dist = -(x*x + y*y)
            if len(heap) == K:
                heapq.heappushpop(heap, (dist, x, y))
            else:
                heapq.heappush(heap, (dist, x, y))
        return [(x,y) for (dist,x, y) in heap]

Insert Interval.png

# 57. Insert Interval
# set of non-overlapping intervals, 
# insert a new interval into the intervals (merge if necessary).
# intervals were initially sorted according to their start times.
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        s, e = newInterval[0], newInterval[1]
        left, right = [], []
        for i in intervals:
            if i[1] < s:
                left += i,
            elif i[0] > e:
                right += i,
            else:
                s = min(s, i[0])
                e = max(e, i[1])
        # return left + [Interval(s, e)] + right
        return left + [[s, e]] + right

Smaller Nums.png

# 315. Count of Smaller Numbers After Self
# number of smaller elements to the right of nums[i].
    
# The smaller numbers on the right of a number ==> 
# jump from its right to its left during a stable sort. 
# So I do mergesort with added tracking of those right-to-left jumps.
class Solution:        
    def countSmaller(self, nums: List[int]) -> List[int]:
        def sort(enum):
            half = len(enum) // 2
            if half:
                left, right = sort(enum[:half]), sort(enum[half:])
                for i in range(len(enum))[::-1]:
                    if not right or left and left[-1][1] > right[-1][1]:
                        smaller[left[-1][0]] += len(right)
                        enum[i] = left.pop()
                    else:
                        enum[i] = right.pop()
            return enum
        smaller = [0] * len(nums)
        sort(list(enumerate(nums)))
        return smaller
    
    
# First get rank, the smallest number will be rank 1, the second smallest will be rank 2...
# With this rank info binary indexed tree can be used to count smaller numbers as we scan from right to left.
class Solution:    
    def countSmaller(self, nums):
        rank, N, res = {val: i + 1 for i, val in enumerate(sorted(nums))}, len(nums), []
        BITree = [0] * (N + 1)    
        def update(i):
            while i <= N:
                BITree[i] += 1
                i += (i & -i)   
        def getSum(i):
            s = 0
            while i:
                s += BITree[i]
                i -= (i & -i)
            return s
        for x in reversed(nums):
            res += getSum(rank[x] - 1),
            update(rank[x])
        return res[::-1]