Paste Search Dynamic
jobScheduling
  1. import bisect
  2.  
  3. def jobScheduling(startTime, endTime, profit):
  4.     jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])
  5.     dp = [[0, 0]]
  6.     intervals=[0]
  7.     for s, e, p in jobs:
  8.         i = bisect.bisect(dp, [s + 1]) - 1
  9.         if dp[i][1] + p > dp[-1][1]:
  10.             dp.append([e, dp[i][1] + p])
  11.             intervals.append(intervals[i]+1)
  12.     return [dp[-1][1], intervals[-1]]
  13.  
  14. n = int(input())
  15. startTime, endTime, profit = [], [], []
  16. for _ in range(n):
  17.     startTime.append(int(input()))
  18.     endTime.append(int(input()))
  19.     profit.append(int(input()))
  20. totProf, intervalUsed = jobScheduling(startTime, endTime, profit)
  21. print(sum(profit) - totProf)
  22. print(n - intervalUsed)
Parsed in 0.006 seconds