# 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 result
# 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
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 result
# 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)
Optimize with binary search: O(NlogN) and zip/unzip
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)
Sort by end, based on how many jobs has been completed