diff options
author | Jack Sangdahl <[email protected]> | 2025-03-26 01:37:08 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-26 01:37:08 -0600 |
commit | 4772cdabe0a208eca2e63d5eb56b3f0bc2164eeb (patch) | |
tree | 57a4b94c011ecce8392682afc7b03d695e23db87 /min_num_work_session.py | |
parent | d95541ed50562a0b6b8deeff1a9eacaef7e4c6dc (diff) | |
download | leetcode-4772cdabe0a208eca2e63d5eb56b3f0bc2164eeb.tar.gz leetcode-4772cdabe0a208eca2e63d5eb56b3f0bc2164eeb.zip |
1986. minimum number of work sessions to finish the tasks
Diffstat (limited to 'min_num_work_session.py')
-rw-r--r-- | min_num_work_session.py | 41 |
1 files changed, 41 insertions, 0 deletions
diff --git a/min_num_work_session.py b/min_num_work_session.py new file mode 100644 index 0000000..9c0ca12 --- /dev/null +++ b/min_num_work_session.py @@ -0,0 +1,41 @@ +# 1986. Minimum Number of Work Sessions to Finish the Tasks + +""" +there are 'n' tasks assigned to you. the task times are represented as an +integer array 'tasks' of length 'n' where the i'th task takes 'tasks[i]' +hours to finish. a work session is when you work for at most 'sessionTime' +consecutive hours, and then take a break. given 'tasks' and 'sessionTime', +return the minimum number of work sessions needed to finish all the tasks +following the conditions. the tests are generated such that 'sessionTime' is +greater or equal to the maximum element in 'tasks[i]'. +""" + + +class Solution(object): + def minSessions(self, tasks, sessionTime): + """ + :type tasks: List[int] + :type sessionTime: int + :rtype: int + """ + n = len(tasks) + + def dp(mask): + if mask == 0: + return (1, 0) + res = (float("inf"), float("inf")) + for i in range(n): + if mask & (1 << i): + pieces, prev = dp(mask - (1 << i)) + full = prev + tasks[i] > sessionTime + res = min(res, (pieces + full, tasks[i] + (1 - full) * prev)) + return res + + return dp((1 << n) - 1)[0] + + +if __name__ == "__main__": + obj = Solution() + print(obj.minSessions(tasks=[1, 2, 3], sessionTime=3)) + print(obj.minSessions(tasks=[3, 1, 3, 1, 1], sessionTime=8)) + print(obj.minSessions(tasks=[1, 2, 3, 4, 5], sessionTime=15)) |