Code

[{"language":"C++","code":"class Solution {\npublic:\n    vector<int> maximumWeight(vector<vector<int>>& intervals) {\n        int n = intervals.size();\n        \n        // Add original indices to intervals\n        for (int i = 0; i < n; ++i) {\n            intervals[i].push_back(i);\n        }\n        \n        // Sort by start time\n        sort(intervals.begin(), intervals.end());\n        \n        // Precompute next non-overlapping interval for each interval\n        vector<int> nxt(n);\n        for (int i = 0; i < n; ++i) {\n            int end = intervals[i][1];\n            int l = 0, r = n;\n            while (l < r) {\n                int m = (l + r) / 2;\n                if (intervals[m][0] > end) r = m;\n                else l = m + 1;\n            }\n            nxt[i] = l;\n        }\n        \n        const int INF = 1e9;\n        vector<vector<int64_t>> dp(n + 1, vector<int64_t>(5, 0));\n        vector<vector<array<int, 4>>> choose(n + 1, vector<array<int, 4>>(5, {INF, INF, INF, INF}));\n        \n        // DP backwards\n        for (int i = n - 1; i >= 0; --i) {\n            for (int c = 3; c >= 0; --c) {\n                // Option 1: Skip current interval\n                int64_t skip = dp[i + 1][c];\n                array<int, 4> svec = choose[i + 1][c];\n                \n                // Option 2: Take current interval\n                int64_t take = dp[nxt[i]][c + 1] + intervals[i][2];\n                array<int, 4> tvec = choose[nxt[i]][c + 1];\n                tvec[3] = intervals[i][3]; // Add current interval's original index\n                sort(tvec.begin(), tvec.end());\n                \n                // Choose better option (or lexicographically smaller if equal)\n                if (skip > take || (skip == take && svec < tvec)) {\n                    dp[i][c] = skip;\n                    choose[i][c] = svec;\n                } else {\n                    dp[i][c] = take;\n                    choose[i][c] = tvec;\n                }\n            }\n        }\n        \n        // Extract result\n        vector<int> ans;\n        for (int id : choose[0][0]) {\n            if (id != INF) ans.push_back(id);\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">    vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">> </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">maximumWeight</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">>></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> intervals</span><span style=\"color:#24292E;--shiki-dark:#
Related Tags
