Problem

You are given a 2D integer array intervals, where intervals[i] = [li, ri, weighti]. Interval i starts at position li and ends at ri, and has a weight of weighti. You can choose up to 4 non-overlapping intervals. The score of the chosen intervals is defined as the total sum of their weights.

Return the lexicographically smallest array of at most 4 indices from intervals with maximum score, representing your choice of non-overlapping intervals.

Two intervals are said to be non-overlapping if they do not share any points. In particular, intervals sharing a left or right boundary are considered overlapping.

Example 1

1
2
3
4
5

Input: intervals = [[1,3,2],[4,5,2],[1,5,5],[6,9,3],[6,7,1],[8,9,1]]
Output: [2,3]
Explanation:
You can choose the intervals with indices 2, and 3 with respective weights of
5, and 3.

Example 2

1
2
3
4
5
6

Input: intervals =
[[5,8,1],[6,7,7],[4,7,3],[9,10,6],[7,8,2],[11,14,3],[3,5,5]]
Output: [1,3,5,6]
Explanation:
You can choose the intervals with indices 1, 3, 5, and 6 with respective
weights of 7, 6, 3, and 5.

Constraints

  • 1 <= intevals.length <= 5 * 10^4
  • intervals[i].length == 3
  • intervals[i] = [li, ri, weighti]
  • 1 <= li <= ri <= 10^9
  • 1 <= weighti <= 10^9

Examples

Solution

Method 1 – Dynamic Programming with Binary Search

Intuition

This is a variant of the weighted interval scheduling problem, but we can select at most 4 non-overlapping intervals. We sort intervals by end time, and for each interval, use DP to track the best score for up to 4 picks. To find the last non-overlapping interval, we use binary search.

Approach

  1. Sort intervals by end time, keeping track of original indices.
  2. For each interval, for each possible number of picks (1 to 4), use binary search to find the last interval that ends before the current one starts.
  3. Use DP: dp[i][k] is the best score using the first i intervals and picking k intervals.
  4. Track the indices for lexicographically smallest answer.
  5. Reconstruct the answer from the DP table.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

class Solution {
public:
    vector<int> maxWeight(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector<tuple<int,int,int,int>> arr;
        for (int i = 0; i < n; ++i) arr.push_back({intervals[i][1], intervals[i][0], intervals[i][2], i});
        sort(arr.begin(), arr.end());
        vector<int> ends(n);
        for (int i = 0; i < n; ++i) ends[i] = get<0>(arr[i]);
        vector<vector<long long>> dp(n+1, vector<long long>(5, 0));
        vector<vector<vector<int>>> idx(n+1, vector<vector<int>>(5));
        for (int i = 1; i <= n; ++i) {
            for (int k = 1; k <= 4; ++k) {
                int l = lower_bound(ends.begin(), ends.end(), get<1>(arr[i-1])) - ends.begin();
                if (dp[i-1][k] > dp[l][k-1] + get<2>(arr[i-1])) {
                    dp[i][k] = dp[i-1][k];
                    idx[i][k] = idx[i-1][k];
                } else if (dp[i-1][k] < dp[l][k-1] + get<2>(arr[i-1])) {
                    dp[i][k] = dp[l][k-1] + get<2>(arr[i-1]);
                    idx[i][k] = idx[l][k-1];
                    idx[i][k].push_back(get<3>(arr[i-1]));
                } else {
                    auto a = idx[i-1][k], b = idx[l][k-1];
                    b.push_back(get<3>(arr[i-1]));
                    if (a < b) {
                        dp[i][k] = dp[i-1][k];
                        idx[i][k] = a;
                    } else {
                        dp[i][k] = dp[l][k-1] + get<2>(arr[i-1]);
                        idx[i][k] = b;
                    }
                }
            }
        }
        long long best = 0;
        vector<int> ans;
        for (int k = 1; k <= 4; ++k) {
            if (dp[n][k] > best) {
                best = dp[n][k];
                ans = idx[n][k];
            } else if (dp[n][k] == best && (!ans.size() || idx[n][k] < ans)) {
                ans = idx[n][k];
            }
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};
1

// Omitted for brevity, similar to C++
1

// Omitted for brevity, similar to C++
1

// Omitted for brevity, similar to C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution:
    def maxWeight(self, intervals: list[list[int]]) -> list[int]:
        n = len(intervals)
        arr = sorted([(r, l, w, i) for i, (l, r, w) in enumerate(intervals)])
        ends = [r for r, l, w, i in arr]
        dp = [[0]*5 for _ in range(n+1)]
        idx = [[[] for _ in range(5)] for _ in range(n+1)]
        for i in range(1, n+1):
            for k in range(1, 5):
                l = bisect.bisect_left(ends, arr[i-1][1])
                if dp[i-1][k] > dp[l][k-1] + arr[i-1][2]:
                    dp[i][k] = dp[i-1][k]
                    idx[i][k] = idx[i-1][k][:]
                elif dp[i-1][k] < dp[l][k-1] + arr[i-1][2]:
                    dp[i][k] = dp[l][k-1] + arr[i-1][2]
                    idx[i][k] = idx[l][k-1][:] + [arr[i-1][3]]
                else:
                    a = idx[i-1][k][:]
                    b = idx[l][k-1][:] + [arr[i-1][3]]
                    if a < b:
                        dp[i][k] = dp[i-1][k]
                        idx[i][k] = a
                    else:
                        dp[i][k] = dp[l][k-1] + arr[i-1][2]
                        idx[i][k] = b
        best = 0
        ans = []
        for k in range(1, 5):
            if dp[n][k] > best:
                best = dp[n][k]
                ans = idx[n][k][:]
            elif dp[n][k] == best and (not ans or idx[n][k] < ans):
                ans = idx[n][k][:]
        ans.sort()
        return ans
1

// Omitted for brevity, similar to C++

1

// Omitted for brevity, similar to C++

Complexity

  • ⏰ Time complexity: O(n log n * k), where n is the number of intervals and k=4 is the max number of picks. Each DP step uses binary search.
  • 🧺 Space complexity: O(n * k), for the DP and index tracking arrays.