Minimum Number Of Work Sessions To Finish The Tasks - Leetcode Solution

Problem Statement: You are given an integer array tasks where tasks[i] is the amount of time it takes to complete the ith task.

You want to finish the tasks in a minimum number of work sessions. A work session is a period of time that you work on tasks consecutively. In each work session, you can complete any number of tasks but you must complete all the tasks in the session.

You will be given a positive integer sessionTime which is the maximum time you can spend in a session. You can perform the tasks in any order.

Return the minimum number of work sessions to finish all the tasks.

Solution:

Approach: We can use binary search to find the minimum number of work sessions required to finish the tasks.

We can start by setting the lower limit of our search as 1 as there is always one session required to complete all the tasks. We can set the upper limit as the sum of all the tasks as a single session can finish all the tasks if their total time is less than or equal to sessionTime.

Then, we can perform binary search on the range [1, sum(tasks)]. For each mid value in the search range, we can check if it is possible to finish all the tasks in mid number of sessions or not. To do this, we can check if we can assign tasks to each session such that the time taken in each session is less than or equal to sessionTime. If such an assignment is not possible, we can move our search range to the right half. Otherwise, we can move to the left half.

We can use a helper function isPossible to check if it is possible to complete all the tasks in mid number of sessions or not. This function takes in the current mid value and returns a boolean indicating whether it is possible or not. We can use a backtracking approach to assign tasks to each session and check if the time taken in each session is less than or equal to sessionTime.

Code:

Python

def minSessions(tasks: List[int], sessionTime: int) -> int: def isPossible(mid, tasks, sessionTime, curr_time): if not tasks: return True for i in range(len(curr_time)): if curr_time[i] + tasks[0] <= mid: curr_time[i] += tasks[0] if isPossible(mid, tasks[1:], sessionTime, curr_time): return True curr_time[i] -= tasks[0] if curr_time[i] == 0 or curr_time[i] + tasks[0] == sessionTime: break return False

l, r = 1, sum(tasks)
while l <= r:
    mid = (l + r) // 2
    if isPossible(mid, tasks[1:], sessionTime, [tasks[0]]*mid):
        r = mid - 1
    else:
        l = mid + 1
return l

In this code, we start by initializing our search range as [1, sum(tasks)]. We then perform binary search on this range as described above.

The function isPossible takes in the mid value, the remaining tasks, the sessionTime, and the list of current session times. We initialize the current session times as [tasks[0]]*mid, indicating that we start with the first task in each session. We then iterate over the current session times and try to assign the next task to an available session. If we can find a session to assign a task to, we recursively call isPossible with the updated session times and remaining tasks. If we are able to assign tasks to all sessions such that the time taken in each session is less than or equal to sessionTime, we return True indicating that it is possible to complete all tasks in mid sessions. Otherwise, we return False.

In the main function, we start by setting l and r as 1 and sum(tasks) respectively. We then perform binary search on this range, updating either l or r based on the return value of isPossible. Once l > r, we have found the minimum number of sessions required to complete all tasks.

Time Complexity: The time complexity of this solution is O(n log(sum(tasks))), where n is the length of the tasks array and sum(tasks) is the sum of all the elements of the tasks array.

Explanation: We can start by setting the lower limit of our search as 1 as there is always one session required to complete all the tasks. We can set the upper limit as the sum of all the tasks as a single session can finish all the tasks if their total time is less than or equal to sessionTime.

Then, we can perform binary search on the range [1, sum(tasks)]. For each mid value in the search range, we can check if it is possible to finish all the tasks in mid number of sessions or not. To do this, we can check if we can assign tasks to each session such that the time taken in each session is less than or equal to sessionTime. If such an assignment is not possible, we can move our search range to the right half. Otherwise, we can move to the left half.

We can use a helper function isPossible to check if it is possible to complete all the tasks in mid number of sessions or not. This function takes in the current mid value and returns a boolean indicating whether it is possible or not. We can use a backtracking approach to assign tasks to each session and check if the time taken in each session is less than or equal to sessionTime.

1