# Sample Pattern: Two while loop (the return value is the opposite per problem description)deffindLongestChain(self,pairs: List[List[int]]) ->int: sortedIn =sorted(pairs, key=lambdax: (x[1], x[0])) i =0 result =0while i <len(sortedIn): j = i +1 result +=1while j <len(sortedIn)and sortedIn[j][0] <= sortedIn[i][1]: j +=1 i = jreturn result
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"""classSolution:defemployeeFreeTime(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=lambdax: (x[0], -x[1])) result = [] counter =0 prevPoint =float('-inf')for point in sortedPoints:if counter ==0and prevPoint != point[0]and point[0]!= point[1]and prevPoint !=float('-inf'): result.append(Interval(prevPoint, point[0])) counter = counter + (1if point[1]==1else-1) prevPoint = point[0]return result
# Time limit exceededclassSolution:defjobScheduling(self,startTime: List[int],endTime: List[int],profit: List[int]) ->int: # max profit by using from begin to self.end@lru_cache(maxsize=None)defmaxProfit(begin:int) ->int:if begin >= self.end:return0# job at begin# take take = self.sortedInter[begin][2]for index, zipTuple inenumerate(self.sortedInter[begin+1:], begin+1):if zipTuple[0]>= self.sortedInter[begin][1]: take +=maxProfit(index)break# not take notTake =maxProfit(begin +1)returnmax(take, notTake) self.sortedInter =sorted(zip(startTime, endTime, profit)) self.end =len(self.sortedInter)returnmaxProfit(0)
Optimize with binary search: O(NlogN) and zip/unzip
classSolution:defjobScheduling(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)defmaxProfit(pos:int) ->int:if pos >= self.end:return0# 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)returnmax(take, notTake) self.sortedStart, self.sortedEnd, self.sortedProfit =zip(*sorted(zip(startTime, endTime, profit))) self.end =len(self.sortedStart)returnmaxProfit(0)
Sort by end, based on how many jobs has been completed
classSolution:defjobScheduling(self,startTime: List[int],endTime: List[int],profit: List[int]) ->int:# maximum profit from 0 to pos@lru_cache(maxsize=None)defmaxProfit(pos:int) ->int:if pos <0:return0 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)returnmax(take, notTake) self.sortedEnd, self.sortedStart, self.sortedProfit =zip(*sorted(zip(endTime, startTime, profit)))returnmaxProfit(len(self.sortedEnd) -1)