aboutsummaryrefslogtreecommitdiffstats
path: root/1235
diff options
context:
space:
mode:
Diffstat (limited to '1235')
-rwxr-xr-x1235/main.py37
1 files changed, 37 insertions, 0 deletions
diff --git a/1235/main.py b/1235/main.py
new file mode 100755
index 0000000..ab6c107
--- /dev/null
+++ b/1235/main.py
@@ -0,0 +1,37 @@
+#!/usr/bin/env python
+
+import bisect
+import typing
+
+
+class Solution:
+ def jobScheduling(
+ self,
+ startTime: typing.List[int],
+ endTime: typing.List[int],
+ profit: typing.List[int],
+ ) -> int:
+ jobs = sorted(zip(endTime, startTime, profit))
+
+ number_of_jobs = len(profit)
+
+ dp = [0] * (number_of_jobs + 1)
+
+ for i, (current_end_time, current_start_time, current_profit) in enumerate(
+ jobs
+ ):
+ index = bisect.bisect_right(
+ jobs, current_start_time, hi=i, key=lambda x: x[0]
+ )
+ dp[i + 1] = max(dp[i], dp[index] + current_profit)
+
+ return dp[number_of_jobs]
+
+
+def main():
+ solution = Solution()
+ print(solution.jobScheduling())
+
+
+if __name__ == "__main__":
+ main()