sinkineben | C++ | Binary Search | State compression DP
Analysis\n\nWe should put the tasks into n boxes, the size of each box is sessionTime. And we want to minimize such n.\n\n\n\n## Binary Search\n\n- The min numb
**Analysis**\n\nWe should put the `tasks` into `n` boxes, the size of each box is `sessionTime`. And we want to minimize such `n`.\n\n\n\n## Binary Search\n\n- The min number of sessions we need is `l = SUM(tasks) / sessionTime`.\n- The max number of session we need is `n = tasks.size`.\n- Perform a binary search on this range `[l, n]`, to test each `m` whether if it\'s valid.\n\n```cpp\nclass Solution {\npublic:\n    int minSessions(vector<int>& tasks, int sessionTime) {\n        int n = tasks.size();\n        int total = accumulate(begin(tasks), end(tasks), 0);\n        int l = total / sessionTime, r = n;\n        while (l < r)\n        {\n            int m = l + (r - l) / 2;\n            if (check(tasks, m, sessionTime)) r = m;\n            else l = m + 1;\n        }\n        return l;\n    }\n    \n    /* @sessions - The number of sessions.\n     * @limit - Each session should have >= 1 task, but total time <= limit.\n     */\n    bool check(vector<int> &tasks, int sessions, int limit)\n    {\n        /* there are `sessions` work-sessions, and each session\n         * `assign[i]` should be assigned with >= 1 task\n         */\n        vector<int> assign(sessions, 0);\n        return backtrack(tasks, assign, 0, limit);\n    }\n\n    bool backtrack(vector<int> &tasks, vector<int> &assign, int idx, int limit)\n    {\n        /* When all the tasks have been assigned, then return true. */\n        int n = tasks.size();\n        if (idx >= n) return true;\n\n        int task = tasks[idx];\n        /* For each session `assign[i]`, try to put the `task` on it. */\n        for (int &workload : assign)\n        {\n            if (workload + task <= limit)\n            {\n                workload += task;\n                if (backtrack(tasks, assign, idx + 1, limit)) return true;\n                workload -= task;\n            }\n            /* After assignments(backtracking), there is no task assigned to\n             * current session, the false.\n             */\n            if (workload == 0) return false;\n        }\n        return false;\n    }\n};\n```\n\n\n\n## State Compression DP\n\n**Get time of each subset**\n\n- Use an integer `x` to denote whether if `task[i]` is in the subset. If `(x >> j) & 1`, then `task[j]` is in the subset `x`.\n\n- Let `total[x]` denote the total time of tasks subset `x`, then we have\n\n  ```cpp\n  total[x] = tasks[j] + total[x - (1 << j)] where ((x >> j) & 1) != 0\n  ```\n\n**DP**\n\nLet `dp[x]` denote the min number of sessions, when we have a subset of tasks (denoted by `x`) . \n\nFor each subset `s` of `x`, we can assign `s` with a new session (if the `sessionTime` is large enough to put `s` in).\n\nThen we have\n$$\ndp[x] = \\min_{s \\sube x}\\{ {dp[x -s]} + 1 \\ \\ | \\ \\ \\text{total}[s] \\le \\text{sessionTime} \\}\n$$\n\n```cpp\nclass Solution {\npublic:\n    const int INF = INT_MAX / 2;\n    int minSessions(vector<int>& tasks, int sessionTime) {\n        int n = tasks.size();\n        vector<int> total(1 << n, 0);\n        for (int x = 1; x < (1 << n); ++x)\n        {\n            int j = x & (-x);\n            int idx = __builtin__ctz(j);\n            total[x] = tasks[idx] + total[x - j];\n        }\n        vector<int> dp(1 << n, INF);\n        dp[0] = 0;\n        for (int x = 1; x < (1 << n); ++x)\n        {\n            for (int s = x; s; s = (s - 1) & x)\n                if (total[s] <= sessionTime)\n                \tdp[x] = min(dp[x], dp[x - s] + 1);\n        }\n        return dp.back();\n    }\n};\n```\n\n
['Dynamic Programming', 'C']