The whole problem is weighted interval scheduling with two twists bolted on: you may take at most four intervals, and among all maximum-weight choices you must return the lexicographically smallest list of original indices. Strip those twists away and it is the textbook `dp[i]` = best score using intervals ending at or before position `i`, where taking one jumps back to the last interval that finishes strictly before this one starts. My first instinct was to reach for a greedy: sort by weight, grab the heaviest four that fit. That collapses immediately — a single heavy interval can block two medium ones that together beat it, and greedy has no way to reconsider. So the pick-count has to live inside the DP state, not be resolved afterward. I sort by right endpoint and add a second axis `k` in `{0,1,2,3,4}` for how many intervals I have used. `table[i][k]` holds both the max weight and the actual index set achieving it. When I take interval `i`, I binary-search `prevIdx[i]` — the last interval whose right end is strictly below `i`'s left end (strictly, because sharing a boundary counts as overlapping here) — and chain onto `table[prevIdx[i]][k-1]`. The lexicographic requirement is the part that bites. I keep every candidate's index list sorted ascending and, on a weight tie, prefer the array that is lexicographically smaller. Because I store the winning index set at every subproblem and always propagate the smaller one, the smallest global array falls out at `table[n-1][4]`. ### Worked example Take `intervals = [[1,3,2],[4,5,2],[1,5,5],[6,9,3],[6,7,1],[8,9,1]]`. Sorted by right end the useful candidates are index `2` (`[1,5]`, weight `5`) and index `3` (`[6,9]`, weight `3`); they do not share a point since `6 > 5`. Their combined weight is `8`, beating any single interval and any other non-overlapping pair. The answer is `[2,3]` — already sorted, already lexicographically minimal. ### Complexity - Time O(n log n) — one sort, then for each of the `n` intervals a binary search for `prevIdx[i]` and a constant `k <= 4` transitions, each copying an index list of length at most 4. - Space O(n) — the DP table stores one small state (weight plus up to four indices) per interval per `k`, and `k` is bounded by 5. ### Code (C++) ```cpp class Solution { public: vector maximumWeight(vector>& intervals) { int n = intervals.size(); // order[]: intervals sorted by right endpoint (then left), carrying original index vector order(n); for (int i = 0; i < n; ++i) order[i] = i; sort(order.begin(), order.end(), [&](int a, int b) { if (intervals[a][1] != intervals[b][1]) return intervals[a][1] < intervals[b][1]; return intervals[a][0] < intervals[b][0]; }); // Sorted arrays for binary search / DP vector L(n), R(n), W(n); vector orig(n); for (int i = 0; i < n; ++i) { orig[i] = order[i]; L[i] = intervals[order[i]][0]; R[i] = intervals[order[i]][1]; W[i] = intervals[order[i]][2]; } // p[i] = number of intervals (in sorted order) whose R < L[i]; i.e. the count of // valid predecessors -> next usable start index when we "take" interval i is p[i]. // We iterate DP forward over sorted position; taking i jumps to prev[i] = last j with R[j] < L[i]. // prev[i] as an index into sorted array: greatest j such that R[j] < L[i], else -1. vector prevIdx(n); for (int i = 0; i < n; ++i) { // binary search largest j with R[j] < L[i] int lo = 0, hi = n - 1, res = -1; while (lo <= hi) { int mid = (lo + hi) / 2; if (R[mid] < L[i]) { res = mid; lo = mid + 1; } else hi = mid - 1; } prevIdx[i] = res; } // dp[i][k]: best result considering the PREFIX of sorted intervals 0..i (inclusive), // choosing at most k of them. Store weight + the chosen ORIGINAL indices (kept sorted asc). // We build forward: dp over i from 0..n-1. // Value = pair(weight, vector sorted-original-indices, lexicographically smallest). struct St { long long w; vector idx; // original indices, kept sorted ascending }; // better(a,b): true if a is strictly better than b (max weight, then lex-smaller idx array) auto better = [](const St& a, const St& b) -> bool { if (a.w != b.w) return a.w > b.w; return a.idx < b.idx; // lexicographically smaller wins on tie }; const int K = 4; // dp indexed by k (0..4). dpPrev = dp for prefix i-1. dpCur for prefix i. // dp[k] = best using at most k picks among first (i+1) sorted intervals. vector dp(K + 1); for (int k = 0; k <= K; ++k) dp[k] = St{0, {}}; // We need dp values at prefix prevIdx[i] to take interval i. Store snapshots per prefix. // n up to 5e4, K=4 -> storing all prefixes is 2.5e5 St objects; idx vectors <=4 ints. OK. vector> table(n); // table[i] = dp array (k=0..K) for prefix 0..i for (int i = 0; i < n; ++i) { vector cur(K + 1); // base: at most 0 picks cur[0] = St{0, {}}; for (int k = 1; k <= K; ++k) { // option A: don't use interval i -> best from prefix i-1 with at most k St best = (i == 0) ? St{0, {}} : table[i-1][k]; // option B: use interval i -> weight[i] + dp[prevIdx[i]][k-1], add orig[i] St take; take.w = W[i]; take.idx.clear(); if (prevIdx[i] >= 0) { const St& sub = table[prevIdx[i]][k-1]; take.w += sub.w; take.idx = sub.idx; } take.idx.push_back(orig[i]); sort(take.idx.begin(), take.idx.end()); if (better(take, best)) best = take; cur[k] = best; } table[i] = move(cur); } if (n == 0) return {}; return table[n-1][K].idx; } }; ``` ### One note The boundary rule is the trap. "Non-overlapping" here means intervals may not share even a single point, so `[1,5]` and `[5,8]` still conflict. That forces the predecessor test to be `R[j] < L[i]` with a strict `<`, not `<=`. Get that comparison wrong by one and you happily stack intervals that touch at an endpoint, quietly overcounting weight on exactly the inputs designed to catch it. The transferable lesson: whenever a scheduling problem says "non-overlapping," pin down whether shared endpoints are allowed before you write the binary search — that single character decides correctness.