From 41bf9e7f320cacc9e478abb9c468c53e40d0fde3 Mon Sep 17 00:00:00 2001 From: terminaldweller Date: Fri, 5 Jan 2024 22:52:04 -0500 Subject: 1235 --- 1235/main.py | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+) create mode 100755 1235/main.py (limited to '1235') 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() -- cgit v1.2.3