Java O(n! log(n)) Binary Search + Recursion (0ms, beats 100%)
Instead of searching for the best answer using classic recursion + pruning, assume the aswer and check if it\'s possible to reach it. Search scope for given con
Instead of searching for the best answer using classic recursion + pruning, assume the aswer and check if it\'s possible to reach it. Search scope for given constraints is very small. Sorting elements desc, allows to verify asserted value much faster.\n`sessions` store all times assigned to days `k` so far.\n`si `- index of current last session, so `si + 1` - number of sessions.\n\nComplexity analysis:\nIn recursive function, first task can go into first session only, second task can go to first session or new session, ... nth task can go to each `n` sessions. Recursion time complexity is then `O(n!)`. Binary search adds` log(n) `factor, so the overall time complexity is `O(n! log(n))`. \n\n```\n   public int minSessions(int[] tasks, int sessionTime) {\n        sortDescending(tasks);\n        int l = 1;\n        int r = tasks.length;\n        while (l < r) {\n            int maxSessions = (l + r) / 2;\n            if (canSchedule(maxSessions, tasks, sessionTime, 0, 0, new int[tasks.length])) {\n                r = maxSessions;\n            } else {\n                l = maxSessions + 1;\n            }\n        }\n        return l;\n    }\n\n    boolean canSchedule(int max, int[] tasks, int sessionTime, int k, int si, int sessions[]) {\n        if (si + 1 > max) return false;\n        else if (k == tasks.length || max == tasks.length) return true;\n        else {\n            int t = tasks[k]; \n            for (int i = 0; i <= si + 1; i++) { //iterate all current started sessions and si + 1 (new empty session)\n                if (sessions[i] + t <= sessionTime) {\n                    sessions[i] += t;\n                    if (canSchedule(max, tasks, sessionTime, k + 1, Math.max(si, i), sessions)) return true;\n                    sessions[i] -= t;\n                }\n            }\n            return false;\n        }\n    }\n\n    private void sortDescending(int[] tasks) {\n        Arrays.sort(tasks);\n        int i = 0;\n        while (i < tasks.length / 2) {\n            int j = tasks.length - i - 1;\n            int tmp = tasks[i];\n            tasks[i] = tasks[j];\n            tasks[j] = tmp;\n            i++;\n        }\n    }\n```
['Recursion', 'Binary Tree']