Minimum Number of Work Sessions to Finish the Tasks

Medium

Swiggy

4 views

Topics:

ArraysDynamic ProgrammingBit Manipulation

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.

You should finish the given tasks in a way that satisfies the following conditions:

If you start a task in a work session, you must complete it in the same work session.
You can start a new task immediately after finishing the previous one.
You may complete the tasks in any order.

Given tasks and sessionTime, return the minimum number of work sessions needed to finish all the tasks following the conditions above.

The tests are generated such that sessionTime is greater than or equal to the maximum element in tasks[i].

Example 1:

Input: tasks = [1,2,3], sessionTime = 3
Output: 2
Explanation: You can finish the tasks in two work sessions.
- First work session: finish the first and the second tasks in 1 + 2 = 3 hours.
- Second work session: finish the third task in 3 hours.

Example 2:

Input: tasks = [3,1,3,1,1], sessionTime = 8
Output: 2
Explanation: You can finish the tasks in two work sessions.
- First work session: finish all the tasks except the last one in 3 + 1 + 3 + 1 = 8 hours.
- Second work session: finish the last task in 1 hour.

Example 3:

Input: tasks = [1,2,3,4,5], sessionTime = 15
Output: 1
Explanation: You can finish all the tasks in one work session.

Constraints:

n == tasks.length
1 <= n <= 14
1 <= tasks[i] <= 10
max(tasks[i]) <= sessionTime <= 15

Try coding it in LeetCode

Minimum Number of Work Sessions to Finish the Tasks

Medium

Swiggy

4 views

Topics:

ArraysDynamic ProgrammingBit Manipulation

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.

You should finish the given tasks in a way that satisfies the following conditions:

If you start a task in a work session, you must complete it in the same work session.
You can start a new task immediately after finishing the previous one.
You may complete the tasks in any order.

Given tasks and sessionTime, return the minimum number of work sessions needed to finish all the tasks following the conditions above.

The tests are generated such that sessionTime is greater than or equal to the maximum element in tasks[i].

Example 1:

Input: tasks = [1,2,3], sessionTime = 3
Output: 2
Explanation: You can finish the tasks in two work sessions.
- First work session: finish the first and the second tasks in 1 + 2 = 3 hours.
- Second work session: finish the third task in 3 hours.

Example 2:

Input: tasks = [3,1,3,1,1], sessionTime = 8
Output: 2
Explanation: You can finish the tasks in two work sessions.
- First work session: finish all the tasks except the last one in 3 + 1 + 3 + 1 = 8 hours.
- Second work session: finish the last task in 1 hour.

Example 3:

Input: tasks = [1,2,3,4,5], sessionTime = 15
Output: 1
Explanation: You can finish all the tasks in one work session.

Constraints:

n == tasks.length
1 <= n <= 14
1 <= tasks[i] <= 10
max(tasks[i]) <= sessionTime <= 15

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the task durations? Can a task have a duration of 0, or be negative?
What is the maximum allowed session duration, and what data type is it (integer, float)?
If it's impossible to complete all tasks within any number of sessions given the maximum session duration, what should I return?
Is the order of tasks within a session important? Does rearranging the order of tasks affect the number of sessions needed?
Can I assume that the input array is non-empty, or should I handle the case where the task list is empty?

Brute Force Solution

Approach

The goal is to figure out the fewest number of work sessions needed to complete all tasks, given a maximum work time for each session. The brute force method explores every single possible combination of tasks assigned to each session. It is like trying every possible grouping of tasks.

Here's how the algorithm would work step-by-step:

Start by considering a single work session. Try putting one task in that session, then two tasks, then three, and so on, until you've tried all possible combinations of tasks in just one session.
Check if any of these single session combinations can accommodate all the tasks within the session's maximum work time. If so, that's a solution.
If no single session works, move on to considering two work sessions. Now, systematically explore all possible ways to divide the tasks into these two sessions.
For each combination of tasks, check if each session's total work time stays within the limit.
If a valid combination is found (meaning both sessions stay within their time limit), you've found a potential solution with two sessions.
If no two-session solution works, move on to three sessions, then four, and so on. Repeat the process of trying every possible combination and checking if all sessions respect the time constraint.
Continue until you find a combination that works, and note the number of sessions required for that combination. Since we started with the fewest sessions and worked our way up, this solution will be the minimum number of sessions required.

Code Implementation

def solve():
    tasks = [4, 5, 2, 4, 5]
    session_time_limit = 8

    number_of_tasks = len(tasks)

    # Iterate through the possible number of sessions
    for number_of_sessions in range(1, number_of_tasks + 1):
        for combination in generate_combinations(tasks, number_of_sessions):

            # Check if the combination is valid
            is_valid = True
            for session in combination:
                if sum(session) > session_time_limit:
                    is_valid = False
                    break

            if is_valid:
                return number_of_sessions

    return -1

def generate_combinations(tasks, number_of_sessions):
    if number_of_sessions == 1:
        yield [tasks]
        return

    if not tasks:
        yield [[] for _ in range(number_of_sessions)]
        return

    first_task = tasks[0]
    remaining_tasks = tasks[1:]

    for combination in generate_combinations(remaining_tasks, number_of_sessions):
        for session_index in range(number_of_sessions):
            new_combination = [session[:] for session in combination]
            new_combination[session_index] = [first_task] + new_combination[session_index]
            yield new_combination

print(solve())

def solve():
    tasks = [4, 5, 2, 4, 5]
    session_time_limit = 8
    number_of_tasks = len(tasks)

    for number_of_sessions in range(1, number_of_tasks + 1):

        #Try all possible combinations of dividing the tasks
        for combination in generate_combinations(tasks, number_of_sessions):

            is_valid = True

            #Check if each session's sum is valid
            for session in combination:
                if sum(session) > session_time_limit:
                    is_valid = False
                    break
            
            #If combination is valid, return number of sessions
            if is_valid:
                return number_of_sessions

    return -1

def generate_combinations(tasks, number_of_sessions):

    #Base case for only one session
    if number_of_sessions == 1:
        yield [tasks]
        return

    if not tasks:
        yield [[] for _ in range(number_of_sessions)]
        return

    first_task = tasks[0]
    remaining_tasks = tasks[1:]

    for combination in generate_combinations(remaining_tasks, number_of_sessions):
        for session_index in range(number_of_sessions):
            new_combination = [session[:] for session in combination]
            new_combination[session_index] = [first_task] + new_combination[session_index]
            yield new_combination

print(solve())

Big(O) Analysis

Time Complexity

O(n*2^n) – The brute force approach iterates through all possible combinations of tasks to assign to work sessions. For n tasks, there are 2^n possible subsets. In the worst case, we might need to check all possible combinations up to n sessions. For each session count (from 1 to n), we potentially iterate through all 2^n subsets. Since we check each subset to determine valid groupings of the n tasks across at most n sessions, and each subset check involves examining the n tasks, the algorithm has a time complexity of approximately O(n*2^n).

Space Complexity

O(N) – The brute force approach outlined explores all possible combinations of tasks in different sessions. The dominant space complexity comes from the need to store these combinations which in the worst case could involve storing each of the N tasks within its own session. Thus a significant amount of space may be required to represent this potential arrangement of tasks across sessions. This leads to a space complexity of O(N) where N is the number of tasks.

Optimal Solution

Approach

This problem asks us to minimize the number of work sessions needed to complete a set of tasks, given a constraint on how much work can be done in one session. The key idea is to use a greedy approach. We try to pack as much work as possible into each session before starting a new one.

Here's how the algorithm would work step-by-step:

Consider the tasks in order.
For each task, check if adding it to the current work session would exceed the maximum allowed work.
If adding the task does not exceed the limit, add it to the current session.
If adding the task exceeds the limit, start a new work session and add the task to that new session.
Continue this process until all tasks have been assigned to work sessions.
The total number of work sessions created is the minimum number required.

Code Implementation

def minimum_work_sessions(tasks, session_time):
    number_of_sessions = 0
    current_session_load = 0

    for task_duration in tasks:
        # If adding the task exceeds the limit, start a new session.
        if current_session_load + task_duration > session_time:
            number_of_sessions += 1
            current_session_load = task_duration

        # If the task can be added to the current session, add it.
        else:
            current_session_load += task_duration

    # Need to add a session if any work was done.
    if current_session_load > 0:
        number_of_sessions += 1

    return number_of_sessions

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each task in the input list once. For each task, it performs a constant-time check to see if it fits within the current work session's limit. If it doesn't fit, a new session is started, also a constant-time operation. Therefore, the time complexity is directly proportional to the number of tasks, n, as there are no nested loops or recursion. The number of operations grows linearly with the input size, leading to O(n) time complexity.

Space Complexity

O(1) – The provided algorithm operates in place, iterating through the tasks one by one. It only uses a few constant space variables, like the current work session load and the number of work sessions. It does not create any auxiliary data structures whose size depends on the input size (number of tasks). Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty tasks array	Return 0, indicating no work sessions are needed when there are no tasks.
tasks array with only one task	Return 1, as a single session is sufficient to complete a single task.
sessionTime is zero or negative	Return 0 since no work can be performed in zero or negative time.
Tasks array with very large number of tasks (scalability)	Ensure the algorithm's time complexity is efficient, preferably O(n log n) or O(n*k) for small k if possible, to handle large inputs without exceeding time limits.
All tasks have duration exceeding sessionTime	Return the number of tasks, as each task requires its own session.
Tasks array contains tasks with zero duration	Ignore tasks with zero duration since they do not contribute to the number of sessions required.
sessionTime is very large compared to task durations	The greedy or dynamic programming algorithm should still work correctly, minimizing the number of sessions used as efficiently as possible.
Integer overflow when calculating the number of sessions (large number of tasks and sessions)	Use a data type with sufficient capacity (e.g., long) or consider using a modular arithmetic approach if appropriate.