LeetCode 1986: Minimum Number of Work Sessions to Finish the Tasks Solution

Master LeetCode problem 1986 (Minimum Number of Work Sessions to Finish the Tasks), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1986. Minimum Number of Work Sessions to Finish the Tasks

Medium

Array Dynamic Programming Backtracking Bit Manipulation Bitmask

Problem Explanation

Explanation:

Algorithm: Greedy + Backtracking
We can approach this problem using a greedy backtracking algorithm.
Since the order of completing tasks can be arbitrary, we can start by sorting the tasks in descending order.
We then perform a backtracking search where we try to assign tasks to work sessions in a greedy manner.
At each step, we try to assign the current task to the current work session if it fits within the remaining time of the current session.
If the current task cannot fit in the current session, we start a new work session and recursively try to assign the task to the new session or any existing sessions.
We keep track of the minimum number of work sessions needed to complete all tasks.
We can optimize the backtracking process by keeping track of the minimum number of work sessions found so far and prune branches that exceed this minimum.
Finally, we return the minimum number of work sessions needed.
Time Complexity: The time complexity of this algorithm is O(n!), where n is the number of tasks.
Space Complexity: The space complexity is O(n) for the recursive call stack.

Solution Code

class Solution {
    int minSessions = Integer.MAX_VALUE;

    public int minSessions(int[] tasks, int sessionTime) {
        Arrays.sort(tasks);
        backtrack(tasks, sessionTime, new int[tasks.length], 0, 0);
        return minSessions;
    }

    private void backtrack(int[] tasks, int sessionTime, int[] sessions, int index, int usedSessions) {
        if (usedSessions >= minSessions) return;
        if (index == tasks.length) {
            minSessions = usedSessions;
            return;
        }

        for (int i = 0; i < usedSessions; i++) {
            if (sessions[i] + tasks[index] <= sessionTime) {
                sessions[i] += tasks[index];
                backtrack(tasks, sessionTime, sessions, index + 1, usedSessions);
                sessions[i] -= tasks[index];
            }
        }

        sessions[usedSessions] = tasks[index];
        backtrack(tasks, sessionTime, sessions, index + 1, usedSessions + 1);
        sessions[usedSessions] = 0;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1986 (Minimum Number of Work Sessions to Finish the Tasks)?

This page provides optimized solutions for LeetCode problem 1986 (Minimum Number of Work Sessions to Finish the Tasks) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1986 (Minimum Number of Work Sessions to Finish the Tasks)?

The time complexity for LeetCode 1986 (Minimum Number of Work Sessions to Finish the Tasks) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1986 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1986 in Java, C++, or Python.

Back to LeetCode Solutions