3414. Maximum Score of Non-overlapping Intervals

class Solution {
    public int[] maximumWeight(List<List<Integer>> intervals) {
        int n = intervals.size();
        
        // Step 1: Sort by right endpoint, then by left, then by weight, then by original index
        int[][] arr = new int[n][4]; // [l, r, weight, originalIndex]
        for (int i = 0; i < n; i++) {
            arr[i][0] = intervals.get(i).get(0); // l
            arr[i][1] = intervals.get(i).get(1); // r
            arr[i][2] = intervals.get(i).get(2); // weight
            arr[i][3] = i;                        // original index
        }
        Arrays.sort(arr, (a, b) -> a[1] != b[1] ? a[1] - b[1] : 
                                   a[0] != b[0] ? a[0] - b[0] : 
                                   a[2] != b[2] ? a[2] - b[2] : a[3] - b[3]);
        
        // Step 2: DP
        // dp[k][i] = {maxScore, lexSmallestIndices[]} 
        // choosing k intervals from first i intervals
        // We choose up to 4 intervals
        
        // State: dp[i][k] = best {score, indices[]} using k intervals, last ending at arr[i]
        // For space, store score and index array
        
        long[][] dpScore = new long[n][5];    // dpScore[i][k] = max score with k intervals, i-th as last
        int[][][] dpIdx = new int[n][5][];    // dpIdx[i][k] = lex smallest indices
        
        // Initialize
        for (long[] row : dpScore) Arrays.fill(row, -1);
        
        // Helper: compare two index arrays lexicographically
        // Returns true if a < b
        
        for (int i = 0; i < n; i++) {
            // k=1: just pick interval i
            dpScore[i][1] = arr[i][2];
            dpIdx[i][1] = new int[]{arr[i][3]};
            
            // Binary search for last interval j where arr[j][1] < arr[i][0]
            // (strictly less, since sharing boundary = overlapping)
            int lo = 0, hi = i - 1, prev = -1;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (arr[mid][1] < arr[i][0]) {
                    prev = mid;
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
            
            for (int k = 2; k <= 4; k++) {
                // Option 1: don't pick i → handled when we pick best across all i
                // Option 2: pick i + best (k-1) from prev
                if (prev >= 0) {
                    // Find best dp[j][k-1] for j in 0..prev
                    // (We'll handle this with prefix best arrays)
                }
            }
        }
        
        // Better approach: prefix best dp
        // best[k] = {bestScore, bestIndices} for exactly k chosen intervals so far
        
        long[] bestScore = new long[5];
        int[][] bestIdx = new int[5][];
        Arrays.fill(bestScore, -1);
        
        // dp over sorted intervals
        // For each interval i, we can extend any best[k-1] where last interval doesn't overlap
        
        // Store per-position best
        long[][] posScore = new long[n + 1][5];
        int[][][] posIdx  = new int[n + 1][5][];
        for (long[] row : posScore) Arrays.fill(row, -1);
        
        for (int i = 0; i < n; i++) {
            // Binary search: rightmost j < i where arr[j][1] < arr[i][0]
            int lo = 0, hi = i - 1, prev = -1;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (arr[mid][1] < arr[i][0]) { prev = mid; lo = mid + 1; }
                else hi = mid - 1;
            }
            int p = prev + 1; // prefix index (1-based): best among 0..prev
            
            for (int k = 1; k <= 4; k++) {
                // Don't pick i: carry forward
                posScore[i + 1][k] = posScore[i][k];
                posIdx[i + 1][k]   = posIdx[i][k];
                
                // Pick i: need best (k-1) from 0..prev
                long prevS = (k == 1) ? 0 : posScore[p][k - 1];
                int[] prevI = (k == 1) ? new int[0] : posIdx[p][k - 1];
                
                if (k == 1 || prevS >= 0) {
                    long newScore = prevS + arr[i][2];
                    int[] newIdx = append(prevI, arr[i][3]);
                    Arrays.sort(newIdx);
                    
                    if (posScore[i + 1][k] < newScore || 
                       (posScore[i + 1][k] == newScore && isLess(newIdx, posIdx[i + 1][k]))) {
                        posScore[i + 1][k] = newScore;
                        posIdx[i + 1][k]   = newIdx;
                    }
                }
            }
        }
        
        // Find best across all k=1..4
        long best = -1;
        int[] ans = null;
        for (int k = 1; k <= 4; k++) {
            long s = posScore[n][k];
            int[] idx = posIdx[n][k];
            if (s < 0) continue;
            if (s > best || (s == best && isLess(idx, ans))) {
                best = s;
                ans  = idx;
            }
        }
        
        return ans == null ? new int[0] : ans;
    }
    
    private int[] append(int[] arr, int val) {
        int[] res = new int[arr.length + 1];
        System.arraycopy(arr, 0, res, 0, arr.length);
        res[arr.length] = val;
        return res;
    }
    
    // Returns true if a is lexicographically smaller than b
    private boolean isLess(int[] a, int[] b) {
        if (b == null) return true;
        if (a == null) return false;
        for (int i = 0; i < Math.min(a.length, b.length); i++) {
            if (a[i] != b[i]) return a[i] < b[i];
        }
        return a.length < b.length;
    }
}

class Solution:
    def maximumWeight(self, intervals):
        n = len(intervals)

        # [left, right, weight, originalIndex]
        arr = [
            [intervals[i][0], intervals[i][1], intervals[i][2], i]
            for i in range(n)
        ]

        # Sort by right, then left, then weight, then original index
        arr.sort(key=lambda x: (x[1], x[0], x[2], x[3]))

        # dp[i][k] = best score using first i intervals
        # with exactly k selected intervals
        dp = [[(-1, None) for _ in range(5)] for _ in range(n + 1)]

        def is_less(a, b):
            if b is None:
                return True
            return a < b

        for i in range(n):
            left, right, weight, index = arr[i]

            # Find rightmost interval with end < current start
            lo, hi = 0, i - 1
            prev = -1

            while lo <= hi:
                mid = (lo + hi) // 2

                if arr[mid][1] < left:
                    prev = mid
                    lo = mid + 1
                else:
                    hi = mid - 1

            p = prev + 1

            for k in range(1, 5):
                # Don't choose current interval
                dp[i + 1][k] = dp[i][k]

                # Choose current interval
                if k == 1:
                    prev_score = 0
                    prev_indices = []
                else:
                    prev_score, prev_indices = dp[p][k - 1]

                if k == 1 or prev_score >= 0:
                    new_score = prev_score + weight
                    new_indices = sorted(prev_indices + [index])

                    current_score, current_indices = dp[i + 1][k]

                    if (new_score > current_score or
                        (new_score == current_score and
                         is_less(new_indices, current_indices))):
                        dp[i + 1][k] = (new_score, new_indices)

        # Find maximum score among 1 to 4 intervals
        best_score = -1
        answer = None

        for k in range(1, 5):
            score, indices = dp[n][k]

            if score < 0:
                continue

            if (score > best_score or
                (score == best_score and is_less(indices, answer))):
                best_score = score
                answer = indices

        return answer if answer is not None else []

class Solution {
    bool isLess(const vector<int>& a, const vector<int>& b) {
        if (b.empty()) return true;
        return a < b;
    }

public:
    vector<int> maximumWeight(vector<vector<int>>& intervals) {
        int n = intervals.size();

        // [left, right, weight, originalIndex]
        vector<array<int, 4>> arr(n);

        for (int i = 0; i < n; i++) {
            arr[i] = {
                intervals[i][0],
                intervals[i][1],
                intervals[i][2],
                i
            };
        }

        // Sort by right, then left, then weight, then original index
        sort(arr.begin(), arr.end(),
            [](const auto& a, const auto& b) {
                if (a[1] != b[1]) return a[1] < b[1];
                if (a[0] != b[0]) return a[0] < b[0];
                if (a[2] != b[2]) return a[2] < b[2];
                return a[3] < b[3];
            });

        // dp[i][k] = {maximum score, lexicographically smallest indices}
        vector<vector<pair<long long, vector<int>>>> dp(
            n + 1,
            vector<pair<long long, vector<int>>>(5, {-1, {}})
        );

        for (int i = 0; i < n; i++) {
            int left = arr[i][0];
            int weight = arr[i][2];
            int index = arr[i][3];

            // Find rightmost interval with end < current start
            int lo = 0, hi = i - 1;
            int prev = -1;

            while (lo <= hi) {
                int mid = (lo + hi) / 2;

                if (arr[mid][1] < left) {
                    prev = mid;
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }

            int p = prev + 1;

            for (int k = 1; k <= 4; k++) {
                // Don't choose current interval
                dp[i + 1][k] = dp[i][k];

                long long prevScore;
                vector<int> prevIndices;

                if (k == 1) {
                    prevScore = 0;
                } else {
                    prevScore = dp[p][k - 1].first;
                    prevIndices = dp[p][k - 1].second;
                }

                if (k == 1 || prevScore >= 0) {
                    long long newScore = prevScore + weight;

                    vector<int> newIndices = prevIndices;
                    newIndices.push_back(index);

                    sort(newIndices.begin(), newIndices.end());

                    if (dp[i + 1][k].first < newScore ||
                        (dp[i + 1][k].first == newScore &&
                         isLess(newIndices, dp[i + 1][k].second))) {

                        dp[i + 1][k] = {
                            newScore,
                            newIndices
                        };
                    }
                }
            }
        }

        long long bestScore = -1;
        vector<int> answer;

        // Check answers containing 1 to 4 intervals
        for (int k = 1; k <= 4; k++) {
            long long score = dp[n][k].first;
            vector<int> indices = dp[n][k].second;

            if (score < 0)
                continue;

            if (score > bestScore ||
                (score == bestScore && isLess(indices, answer))) {

                bestScore = score;
                answer = indices;
            }
        }

        return answer;
    }
};

class Solution {
    maximumWeight(intervals) {
        const n = intervals.length;

        // [left, right, weight, originalIndex]
        const arr = intervals.map((interval, i) => [
            interval[0],
            interval[1],
            interval[2],
            i
        ]);

        // Sort by right, then left, then weight, then original index
        arr.sort((a, b) =>
            a[1] - b[1] ||
            a[0] - b[0] ||
            a[2] - b[2] ||
            a[3] - b[3]
        );

        // dp[i][k] = [bestScore, lexicographically smallest indices]
        const dp = Array.from(
            { length: n + 1 },
            () => Array.from({ length: 5 }, () => [-1, null])
        );

        const isLess = (a, b) => {
            if (b === null) return true;

            for (let i = 0; i < Math.min(a.length, b.length); i++) {
                if (a[i] !== b[i]) {
                    return a[i] < b[i];
                }
            }

            return a.length < b.length;
        };

        for (let i = 0; i < n; i++) {
            const [left, right, weight, index] = arr[i];

            // Find rightmost interval with end < current start
            let lo = 0;
            let hi = i - 1;
            let prev = -1;

            while (lo <= hi) {
                const mid = Math.floor((lo + hi) / 2);

                if (arr[mid][1] < left) {
                    prev = mid;
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }

            const p = prev + 1;

            for (let k = 1; k <= 4; k++) {
                // Don't choose current interval
                dp[i + 1][k] = dp[i][k];

                let prevScore;
                let prevIndices;

                if (k === 1) {
                    prevScore = 0;
                    prevIndices = [];
                } else {
                    prevScore = dp[p][k - 1][0];
                    prevIndices = dp[p][k - 1][1];
                }

                if (k === 1 || prevScore >= 0) {
                    const newScore = prevScore + weight;

                    const newIndices = [
                        ...prevIndices,
                        index
                    ].sort((a, b) => a - b);

                    const current = dp[i + 1][k];

                    if (
                        current[0] < newScore ||
                        (current[0] === newScore &&
                         isLess(newIndices, current[1]))
                    ) {
                        dp[i + 1][k] = [
                            newScore,
                            newIndices
                        ];
                    }
                }
            }
        }

        // Find maximum score among 1 to 4 intervals
        let bestScore = -1;
        let answer = null;

        for (let k = 1; k <= 4; k++) {
            const [score, indices] = dp[n][k];

            if (score < 0) continue;

            if (
                score > bestScore ||
                (score === bestScore && isLess(indices, answer))
            ) {
                bestScore = score;
                answer = indices;
            }
        }

        return answer ?? [];
    }
}