Java || Beats 99.37% || 1ms || Binary Search || Backtracking || clear and simple Explanation
\n## Minimum Number of Work Sessions to Finish the Tasks\n\nProblem:\n\nYou are given a set of tasks represented by an integer array tasks, where tasks[i] repre
\n## Minimum Number of Work Sessions to Finish the Tasks\n\n**Problem:**\n\nYou are given a set of tasks represented by an integer array `tasks`, where `tasks[i]` represents the number of hours required to finish the ith task. You work in sessions, where each session has a maximum duration of `sessionTime` hours. You need to find the minimum number of sessions required to finish all the tasks, while following these conditions:\n- Once you start a task in a session, you must complete it in the same session.\n- You can start a new task immediately after finishing the previous one.\n- You may complete the tasks in any order.\n\n**Solution:**\n\nWe can use a binary search approach to find the minimum number of sessions. We sort the tasks array in descending order to prioritize longer tasks. Then, we perform binary search on the range of possible session counts, from 1 to the total number of tasks.\n\nIn each iteration of the binary search, we simulate the distribution of tasks among sessions using a backtracking approach. We check if it is possible to complete all tasks within the given session count. If it is possible, we update the answer and continue searching for a smaller session count. Otherwise, we increase the session count and continue searching.\n\nHere\'s the Java implementation of the solution:\n\n```java\nclass Solution {\n    public int minSessions(int[] tasks, int sessionTime) {\n        // Sort tasks in descending order to prioritize longer tasks\n        Arrays.sort(tasks);\n        reverse(tasks);\n\n        int left = 1; // Minimum session count\n        int right = tasks.length; // Maximum session count\n        int answer = 0; // Minimum number of sessions required\n\n        // Binary search on the range of possible session counts\n        while (left <= right) {\n            int mid = left + (right - left) / 2;\n            int[] workSessions = new int[mid]; // Array to track tasks assigned to each session\n\n            // Check if it\'s possible to complete all tasks within the given session count\n            if (isPossible(0, mid, sessionTime, 0, tasks, workSessions, mid)) {\n                answer = mid; // Update the answer\n                right = mid - 1; // Continue searching for a smaller session count\n            } else {\n                left = mid + 1; // Increase the session count\n            }\n        }\n\n        return answer;\n    }\n\n    // Backtracking function to simulate the distribution of tasks among sessions\n    private static boolean isPossible(int idx, int k, int maxLen, int max, int[] tasks, int[] workSessions, int zeroCount) {\n        if (tasks.length - idx < zeroCount) {\n            return false; // Not enough tasks remaining to fill all sessions\n        }\n\n        if (idx == tasks.length) {\n            if (max > maxLen) {\n                return false; // Current session duration exceeds the maximum session time\n            }\n            return true; // All tasks have been assigned to sessions successfully\n        }\n\n        int currentTask = tasks[idx];\n\n        for (int i = 0; i < k; i++) {\n            if (workSessions[i] + currentTask > maxLen) {\n                continue; // Current task cannot be assigned to this session\n            }\n\n            zeroCount -= workSessions[i] == 0 ? 1 : 0; // Decrement zeroCount if a session becomes non-empty\n            workSessions[i] += currentTask; // Assign the task to the current session\n\n            // Recursively check if it\'s possible to complete remaining tasks with the updated sessions\n            if (isPossible(idx + 1, k, maxLen, Math.max(max, workSessions[i]), tasks, workSessions, zeroCount)) {\n                return true; // Tasks can be completed with the current distribution of sessions\n            }\n\n            workSessions[i] -= currentTask; // Backtrack: Remove the task from the current session\n            zeroCount += workSessions[i] == 0 ? 1 : 0; // Increment zeroCount if a session becomes empty again\n\n            if (workSessions[i] == 0) {\n                break; // Skip empty sessions to avoid redundant iterations\n            }\n        }\n\n        return false; // Unable to complete all tasks with the current distribution of sessions\n    }\n\n    // Utility function to reverse an array\n    private void reverse(int[] arr) {\n        int i = 0, j = arr.length - 1;\n\n        while (i < j) {\n            int temp = arr[i];\n            arr[i] = arr[j];\n            arr[j] = temp;\n            i++;\n            j--;\n        }\n    }\n}\n\n```\n\n**Complexity Analysis:**\n\n- Time Complexity: O(N * log(N) * (2^N)), where N is the number of tasks. The algorithm performs binary search on the range of session counts, and for each iteration, it simulates the distribution of tasks using a backtracking approach. The backtracking has a complexity of O(2^N) in the worst case.\n- Space Complexity: O(N), where N is the number of tasks. We use additional space for the workSessions array.\n\n\n
['Binary Search', 'Backtracking', 'Recursion', 'Java']