- Intervals
452.Minimum-Number-of-Arrows-to-Burst-Balloons (H-)
435.Non-overlapping-Intervals (M+) (aka. 646.Maximum-Length-of-Pair-Chain)
757.Set-Intersection-Size-At-Least-Two (H)
# Sample Pattern: Two while loop (the return value is the opposite per problem description)
def findLongestChain(self, pairs: List[List[int]]) -> int:
sortedIn = sorted(pairs, key=lambda x: (x[1], x[0]))
i = 0
result = 0
while i < len(sortedIn):
j = i + 1
result += 1
while j < len(sortedIn) and sortedIn[j][0] <= sortedIn[i][1]:
j += 1
i = j
return result1751.Maximum-Number-of-Events-That-Can-Be-Attended-II (H)
1326.Minimum-Number-of-Taps-to-Open-to-Water-a-Garden (M+)
# Using leetcode 1326 as an example.
def minTaps(self, n: int, ranges: List[int]) -> int:
intervals = [[i - r, i + r] for i, r in enumerate(ranges)]
sortedIntervals = sorted(intervals, key=lambda x : (x[0], -x[1]))
nextEnd = currEnd = currIndex = 0
numTaps = 0
while currIndex < len(sortedIntervals) and currEnd < n:
# for intervals overlapping with current interval,
# pick the one which has farthest reach
nextIndex = currIndex
while nextIndex < len(sortedIntervals) and sortedIntervals[nextIndex][0] <= currEnd:
# greedily pick the overlapping intervals
nextEnd = max(sortedIntervals[nextIndex][1], nextEnd)
nextIndex += 1
if nextIndex == currIndex:
return -1
else:
numTaps += 1
currIndex = nextIndex
currEnd = nextEnd
return numTaps if currEnd >= n else -1 045.Jump-Game-II (M)
1024.Video-Stitching (M+)
1288.Remove-Covered-Intervals (M+)
# using leetcode 1288 as an example
# Greedily pick the interval which has the earliest starting point and biggest length
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
sortedInter = sorted(intervals, key=lambda x: (x[0], -x[1]))
numRemoved = 0
currIndex = 0
while currIndex < len(sortedInter):
nextStart = currIndex + 1
while nextStart < len(sortedInter) and sortedInter[nextStart][1] <= sortedInter[currIndex][1]:
nextStart += 1
numRemoved += 1
currIndex = nextStart
return len(intervals) - numRemoved- Split intervals into Pair(int start, boolean isStart), Pair(int end, boolean isEnd)
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
boundaryPoints = []
for interval in intervals:
boundaryPoints.append((interval[0], 1))
boundaryPoints.append((interval[1], -1))
boundaryPoints.sort(key=lambda x: (x[0], -x[1]))
result = []
start, end = 0, 0
count = 0
for point in boundaryPoints:
if point[1] == 1:
count += 1
if count == 1:
start = point[0]
else:
count -= 1
if count == 0:
end = point[0]
result.append([start, end])
return result252.Meeting-Rooms (M)
253.Meeting-Rooms-II (M+)
056.Merge-Intervals (M)
057.Insert-Intervals (M)
1272.Remove-Interval (M+) 252.Meeting-Rooms (M)
253.Meeting-Rooms-II (M+)
056.Merge-Intervals (M)
057.Insert-Intervals (M)
732.My-Calendar-III (M)
759.Employee-Free-Time (M+)
798.Smallest-Rotation-with-Highest-Score (H)
995.Minimum-Number-of-K-Consecutive-Bit-Flips (H-)
1094.Car-Pooling (E)
1109.Corporate-Flight-Bookings (M)
1589.Maximum-Sum-Obtained-of-Any-Permutation (M)
1674.Minimum-Moves-to-Make-Array-Complementary (H)
1871.Jump-Game-VII (M+)
1893.Check if All the Integers in a Range Are Covered (E)
850.Rectangle-Area-II (H)
1943.Describe-the-Painting (H-)
732.My-Calendar-III (M)
759.Employee-Free-Time (M+)
798.Smallest-Rotation-with-Highest-Score (H)
995.Minimum-Number-of-K-Consecutive-Bit-Flips (H-)
1094.Car-Pooling (E)
1109.Corporate-Flight-Bookings (M)
1589.Maximum-Sum-Obtained-of-Any-Permutation (M)
1674.Minimum-Moves-to-Make-Array-Complementary (H)
1871.Jump-Game-VII (M+)
1893.Check if All the Integers in a Range Are Covered (E)
850.Rectangle-Area-II (H)
1943.Describe-the-Painting (H-)
436. Find Right Interval - binary search + map - [TODO]
- Here PriorityQueue is also used for sorting purpose but in-house implementation.
- A more complicated solution when compared with OPTIONS 2
- Sort intervals using T/S Complexity: O(nlogn)
sorted(intervals, key=lambda interval: (interval.start, interval.end))
- Count interval start as +1, count interval end as -1
"""
# Definition for an Interval.
class Interval:
def __init__(self, start: int = None, end: int = None):
self.start = start
self.end = end
"""
class Solution:
def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
points = []
for intervalList in schedule:
for interval in intervalList:
points.append((interval.start, 1))
points.append((interval.end, -1))
# when start and end occurs at the same point
# start should come first
sortedPoints = sorted(points, key=lambda x: (x[0], -x[1]))
result = []
counter = 0
prevPoint = float('-inf')
for point in sortedPoints:
if counter == 0 and prevPoint != point[0] and point[0] != point[1] and prevPoint != float('-inf'):
result.append(Interval(prevPoint, point[0]))
counter = counter + (1 if point[1] == 1 else -1)
prevPoint = point[0]
return result1235.Maximum-Profit-in-Job-Scheduling (H-)
# Time limit exceeded
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
# max profit by using from begin to self.end
@lru_cache(maxsize=None)
def maxProfit(begin: int) -> int:
if begin >= self.end:
return 0
# job at begin
# take
take = self.sortedInter[begin][2]
for index, zipTuple in enumerate(self.sortedInter[begin+1:], begin+1):
if zipTuple[0] >= self.sortedInter[begin][1]:
take += maxProfit(index)
break
# not take
notTake = maxProfit(begin + 1)
return max(take, notTake)
self.sortedInter = sorted(zip(startTime, endTime, profit))
self.end = len(self.sortedInter)
return maxProfit(0)class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
# max profit by using from pos to self.end - 1
@lru_cache(maxsize=None)
def maxProfit(pos: int) -> int:
if pos >= self.end:
return 0
# job at pos
# take
take = self.sortedProfit[pos]
index = bisect.bisect_left(self.sortedStart, self.sortedEnd[pos], pos + 1)
take += maxProfit(index)
# not take
notTake = maxProfit(pos + 1)
return max(take, notTake)
self.sortedStart, self.sortedEnd, self.sortedProfit = zip(*sorted(zip(startTime, endTime, profit)))
self.end = len(self.sortedStart)
return maxProfit(0)- https://github.com/wisdompeak/LeetCode/tree/master/Greedy/1235.Maximum-Profit-in-Job-Scheduling
- Similar thought as above
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
# maximum profit from 0 to pos
@lru_cache(maxsize=None)
def maxProfit(pos: int) -> int:
if pos < 0:
return 0
notTake = maxProfit(pos - 1)
take = self.sortedProfit[pos]
# here need to use bisect_right
index = bisect.bisect_right(self.sortedEnd, self.sortedStart[pos])
take += maxProfit(index - 1)
return max(take, notTake)
self.sortedEnd, self.sortedStart, self.sortedProfit = zip(*sorted(zip(endTime, startTime, profit)))
return maxProfit(len(self.sortedEnd) - 1)-
Interval + DP + Binary search
-
TODO
- Use named tuples
- Limitations of lru_cache
- Sorted() key word