Python | DFS + Binary Search | ❌bitmask❌DP | Faster than 99%
Intuition\n Describe your first thoughts on how to solve this problem. \nJust don\'t want to use bitmask and dynamic programming.\n# Approach\n Describe your ap
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nJust don\'t want to use bitmask and dynamic programming.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- How to find the minimum number of sessions? We can use binary search to do this. But different from typical binary search, we use `mid` as the number of sessions we\u2019ll have. If we can successfully allocate time for all the tasks with `mid` sessions, that means we still have the chance to minimize `mid`, i.e., upgrade `r = mid`; otherwise, we have to use larger `mid`, i.e., upgrade `l = mid + 1`. We stop when `l == r`.\n\n- How to determine whether the allocation of time is successful? We design a DFS function called `canFinish(i)`. It upgrades `remainTime` list each time and returns whether `tasks[i]` can be finished.\n- The base case is: if we\u2019ve reached the end of `tasks`, that means all the tasks can be finished, so we return True.\n- The basic idea of `canFinish` is that this function takes care of one task `tasks[i]` each time, allocating time to finish it. Specifically, we traverse the `remainTime` list, if the current `remainTime[j]` is still enough to finish the task `tasks[i]` that we\u2019re about to arrange, there are a few things we need to do:\n  - allocate the time and upgrade the remain time (`remainTime[j] -= tasks[i]`) for next task\u2019s schedule.\n  - since we\u2019ve done with task `tasks[i]`, it\u2019s time to think about whether we can allocate time for the next task `tasks[i+1]`, if it is, return `True`.\n  - But if the deeper level returns `False` to the if statement (`canFinish[i+1]` returns `False`), we know that the allocation won\u2019t let the task been finished, so we have to add back `tasks[i]` to `remainTime[j]`. So only tasks that can be finished are allocated the time they need (subtract `tasks[i]` from remain time).\n  - Then, `j` will move to the next index and  use another session time for allocation, the remaining part is kind of repetitive.\n  - After we add back `tasks[i]`, if `remainTime[j] == sessionTime`, we know that the next task cannot be finished and the remain time is only enough to finish the current task. So, we can just break from the loop and return `False`.\n# Complexity\nMaybe someone could help me with complexity analysis, I\'m really bad at this.\n\n# Code\n```\nclass Solution:\n    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n        def canFinish(i):\n            if i == nTask:\n                return True\n            for j in range(mid):\n                if remainTime[j] >= tasks[i]:\n                    remainTime[j] -= tasks[i]\n                    if canFinish(i + 1):\n                        return True\n                    remainTime[j] += tasks[i]\n                    if remainTime[j] == sessionTime:\n                        break\n            return False                    \n        \n        nTask = len(tasks)\n        l, r = 1, nTask\n        tasks.sort(reverse=True)\n        while l < r:            \n            mid = (l + r) // 2\n            remainTime = [sessionTime] * mid\n            if not canFinish(0):\n                l = mid + 1\n            else:\n                r = mid\n        return l\n```\n# Walk-through\nLet\u2019s walk through an example to help understanding.\n\n```python\ntasks = [5, 4, 5, 2, 1, 3]\nsessionTime = 15\n\n# reversely sorted tasks:\ntasks = [5, 5, 4, 3, 2, 1]\n\n# iter 1\nl = 1\nr = 6\nmid = 3\nremainTime = [15, 15, 15]\n\n#canFinish(0), tasks[0] = 5, j = 0\n remianTime = [10, 15, 15]\n#--canFinish(1), tasks[1] = 5, j = 0\n   remianTime = [5, 15, 15]\n#----canFinish(2), tasks[2] = 4, j = 0\n     remianTime = [1, 15, 15]\n#------canFinish(3), tasks[3] = 3, j = 0\n#      remainTime[j] < tasks[i], j += 1\n#------canFinish(3), tasks[3] = 3, j = 1\n       remianTime = [1, 12, 15]\n#--------canFinish(4), tasks[4] = 2, j = 0\n#        remainTime[j] < tasks[i], j += 1\n#--------canFinish(4), tasks[4] = 2, j = 1\n         remianTime = [1, 10, 15]\n#----------canFinish(5), tasks[5] = 1, j = 0\n           remainTime[j] = [0, 10, 15]   \n#------------canFinish(6), i == nTask, return True\n\n# upgrade r\nr = 3\n---------------------------------------------------\n# iter 2\nl = 1\nr = 3\nmid = 2\nremainTime = [15, 15]\n\n#canFinish(0), tasks[0] = 5, j = 0\n remianTime = [10, 15]\n#--canFinish(1), tasks[1] = 5, j = 0\n   remianTime = [5, 15]\n#----canFinish(2), tasks[2] = 4, j = 0\n     remianTime = [1, 15]\n#------canFinish(3), tasks[3] = 3, j = 0\n#      remainTime[j] < tasks[i], j += 1\n#------canFinish(3), tasks[3] = 3, j = 1\n       remianTime = [1, 12]\n#--------canFinish(4), tasks[4] = 2, j = 0\n#        remainTime[j] < tasks[i], j += 1\n#--------canFinish(4), tasks[4] = 2, j = 1\n         remianTime = [1, 10]\n#----------canFinish(5), tasks[5] = 1, j = 0\n           remainTime[j] = [0, 10]   \n#------------canFinish(6), i == nTask, return True\n\n# upgrade r\nr = 2\n---------------------------------------------------\n# iter 3\nl = 1\nr = 2\nmid = 1\nremainTime = [15]\n\n#canFinish(0), tasks[0] = 5, j = 0\n remianTime = [10]\n#--canFinish(1), tasks[1] = 5, j = 0\n   remianTime = [5]\n#----canFinish(2), tasks[2] = 4, j = 0\n     remianTime = [1]\n#------canFinish(3), tasks[3] = 3, j = 0\n       remianTime = [1]\n#      remainTime[j] < tasks[i], j += 1\n#------canFinish(3), tasks[3] = 3, j = 1\n#      exit for loop, return False\n#----canFinish(2), tasks[2] = 4, j = 0\n\t remianTime = [5]\n#--canFinish(1), tasks[1] = 5, j = 0\n   remianTime = [10]    \n#canFinish(0), tasks[0] = 5, j = 0    \nremianTime = [15]\n\n# remainTime[j] == sessionTime\n# break for loop, return False\n\n# upgrade l\nl = 2 = r\n\n# exit while loop, return 2\n```\n\n![1668760528355.jpg](https://assets.leetcode.com/users/images/0a18f277-be5e-4e3f-8437-0eade10d9c6b_1668760745.4470515.png)\n
['Binary Search', 'Depth-First Search', 'Python3']