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.

Examples

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

Solution

Method 1 – Dynamic Programming with Binary Search

Intuition

This problem can be solved using a 0/1 knapsack approach since we need to choose at most 4 intervals. The key insight is to sort intervals by their start time and use dynamic programming to track the maximum weight achievable when selecting exactly j intervals ending at position i. For each interval, we can either skip it or take it (if it doesn’t overlap with previously selected intervals).

Approach

  1. Sort intervals by start time l, and append original indices to track the answer.
  2. Precompute the next non-overlapping interval for each interval using binary search to find the first interval that starts after the current interval ends.
  3. Use DP where dp[i][j] represents the maximum weight when considering intervals from position i onwards and selecting exactly j intervals.
  4. Also track choose[i][j] to store the indices of selected intervals for reconstruction.
  5. For each interval, apply 0/1 knapsack logic: either skip the current interval or take it (and jump to the next non-overlapping interval).
  6. When weights are equal, choose the lexicographically smaller index combination.
  7. Process DP backwards from the last interval to the first.

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62

class Solution {
public:
    vector<int> maximumWeight(vector<vector<int>>& intervals) {
        int n = intervals.size();
        
        // Add original indices to intervals
        for (int i = 0; i < n; ++i) {
            intervals[i].push_back(i);
        }
        
        // Sort by start time
        sort(intervals.begin(), intervals.end());
        
        // Precompute next non-overlapping interval for each interval
        vector<int> nxt(n);
        for (int i = 0; i < n; ++i) {
            int end = intervals[i][1];
            int l = 0, r = n;
            while (l < r) {
                int m = (l + r) / 2;
                if (intervals[m][0] > end) r = m;
                else l = m + 1;
            }
            nxt[i] = l;
        }
        
        const int INF = 1e9;
        vector<vector<int64_t>> dp(n + 1, vector<int64_t>(5, 0));
        vector<vector<array<int, 4>>> choose(n + 1, vector<array<int, 4>>(5, {INF, INF, INF, INF}));
        
        // DP backwards
        for (int i = n - 1; i >= 0; --i) {
            for (int c = 3; c >= 0; --c) {
                // Option 1: Skip current interval
                int64_t skip = dp[i + 1][c];
                array<int, 4> svec = choose[i + 1][c];
                
                // Option 2: Take current interval
                int64_t take = dp[nxt[i]][c + 1] + intervals[i][2];
                array<int, 4> tvec = choose[nxt[i]][c + 1];
                tvec[3] = intervals[i][3]; // Add current interval's original index
                sort(tvec.begin(), tvec.end());
                
                // Choose better option (or lexicographically smaller if equal)
                if (skip > take || (skip == take && svec < tvec)) {
                    dp[i][c] = skip;
                    choose[i][c] = svec;
                } else {
                    dp[i][c] = take;
                    choose[i][c] = tvec;
                }
            }
        }
        
        // Extract result
        vector<int> ans;
        for (int id : choose[0][0]) {
            if (id != INF) ans.push_back(id);
        }
        return ans;
    }
};
 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

import "sort"

func maximumWeight(intervals [][]int) []int {
    n := len(intervals)
    
    // Add original indices to intervals
    for i := 0; i < n; i++ {
        intervals[i] = append(intervals[i], i)
    }
    
    // Sort by start time
    sort.Slice(intervals, func(i, j int) bool {
        if intervals[i][0] != intervals[j][0] {
            return intervals[i][0] < intervals[j][0]
        }
        if intervals[i][1] != intervals[j][1] {
            return intervals[i][1] < intervals[j][1]
        }
        return intervals[i][2] < intervals[j][2]
    })
    
    // Precompute next non-overlapping interval for each interval
    nxt := make([]int, n)
    for i := 0; i < n; i++ {
        end := intervals[i][1]
        l, r := 0, n
        for l < r {
            m := (l + r) / 2
            if intervals[m][0] > end {
                r = m
            } else {
                l = m + 1
            }
        }
        nxt[i] = l
    }
    
    const INF = 1e9
    dp := make([][]int64, n+1)
    choose := make([][][4]int, n+1)
    for i := 0; i <= n; i++ {
        dp[i] = make([]int64, 5)
        choose[i] = make([][4]int, 5)
        for j := 0; j < 5; j++ {
            choose[i][j] = [4]int{INF, INF, INF, INF}
        }
    }
    
    // DP backwards
    for i := n - 1; i >= 0; i-- {
        for c := 3; c >= 0; c-- {
            // Option 1: Skip current interval
            skip := dp[i+1][c]
            svec := choose[i+1][c]
            
            // Option 2: Take current interval
            take := dp[nxt[i]][c+1] + int64(intervals[i][2])
            tvec := choose[nxt[i]][c+1]
            tvec[3] = intervals[i][3] // Add current interval's original index
            sort.Ints(tvec[:])
            
            // Choose better option (or lexicographically smaller if equal)
            if skip > take || (skip == take && less(svec, tvec)) {
                dp[i][c] = skip
                choose[i][c] = svec
            } else {
                dp[i][c] = take
                choose[i][c] = tvec
            }
        }
    }
    
    // Extract result
    var ans []int
    for _, id := range choose[0][0] {
        if id != INF {
            ans = append(ans, id)
        }
    }
    return ans
}

func less(a, b [4]int) bool {
    for i := 0; i < 4; i++ {
        if a[i] != b[i] {
            return a[i] < b[i]
        }
    }
    return false
}
 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

import java.util.*;

class Solution {
    public int[] maximumWeight(int[][] intervals) {
        int n = intervals.length;
        
        // Add original indices to intervals
        int[][] newIntervals = new int[n][4];
        for (int i = 0; i < n; i++) {
            newIntervals[i][0] = intervals[i][0]; // start
            newIntervals[i][1] = intervals[i][1]; // end
            newIntervals[i][2] = intervals[i][2]; // weight
            newIntervals[i][3] = i; // original index
        }
        
        // Sort by start time
        Arrays.sort(newIntervals, (a, b) -> {
            if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
            if (a[1] != b[1]) return Integer.compare(a[1], b[1]);
            return Integer.compare(a[2], b[2]);
        });
        
        // Precompute next non-overlapping interval for each interval
        int[] nxt = new int[n];
        for (int i = 0; i < n; i++) {
            int end = newIntervals[i][1];
            int l = 0, r = n;
            while (l < r) {
                int m = (l + r) / 2;
                if (newIntervals[m][0] > end) {
                    r = m;
                } else {
                    l = m + 1;
                }
            }
            nxt[i] = l;
        }
        
        final int INF = (int) 1e9;
        long[][] dp = new long[n + 1][5];
        int[][][] choose = new int[n + 1][5][4];
        
        // Initialize choose arrays with INF
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < 5; j++) {
                Arrays.fill(choose[i][j], INF);
            }
        }
        
        // DP backwards
        for (int i = n - 1; i >= 0; i--) {
            for (int c = 3; c >= 0; c--) {
                // Option 1: Skip current interval
                long skip = dp[i + 1][c];
                int[] svec = choose[i + 1][c].clone();
                
                // Option 2: Take current interval
                long take = dp[nxt[i]][c + 1] + newIntervals[i][2];
                int[] tvec = choose[nxt[i]][c + 1].clone();
                tvec[3] = newIntervals[i][3]; // Add current interval's original index
                Arrays.sort(tvec);
                
                // Choose better option (or lexicographically smaller if equal)
                if (skip > take || (skip == take && compare(svec, tvec) < 0)) {
                    dp[i][c] = skip;
                    choose[i][c] = svec;
                } else {
                    dp[i][c] = take;
                    choose[i][c] = tvec;
                }
            }
        }
        
        // Extract result
        List<Integer> result = new ArrayList<>();
        for (int id : choose[0][0]) {
            if (id != INF) {
                result.add(id);
            }
        }
        
        return result.stream().mapToInt(i -> i).toArray();
    }
    
    private int compare(int[] a, int[] b) {
        for (int i = 0; i < 4; i++) {
            if (a[i] != b[i]) {
                return Integer.compare(a[i], b[i]);
            }
        }
        return 0;
    }
}
 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

class Solution {
    fun maximumWeight(intervals: Array<IntArray>): IntArray {
        val n = intervals.size
        
        // Add original indices to intervals
        val newIntervals = Array(n) { i ->
            intArrayOf(intervals[i][0], intervals[i][1], intervals[i][2], i)
        }
        
        // Sort by start time
        newIntervals.sortWith { a, b ->
            when {
                a[0] != b[0] -> a[0].compareTo(b[0])
                a[1] != b[1] -> a[1].compareTo(b[1])
                else -> a[2].compareTo(b[2])
            }
        }
        
        // Precompute next non-overlapping interval for each interval
        val nxt = IntArray(n)
        for (i in 0 until n) {
            val end = newIntervals[i][1]
            var l = 0
            var r = n
            while (l < r) {
                val m = (l + r) / 2
                if (newIntervals[m][0] > end) {
                    r = m
                } else {
                    l = m + 1
                }
            }
            nxt[i] = l
        }
        
        val INF = 1_000_000_000
        val dp = Array(n + 1) { LongArray(5) }
        val choose = Array(n + 1) { Array(5) { IntArray(4) { INF } } }
        
        // DP backwards
        for (i in n - 1 downTo 0) {
            for (c in 3 downTo 0) {
                // Option 1: Skip current interval
                val skip = dp[i + 1][c]
                val svec = choose[i + 1][c].clone()
                
                // Option 2: Take current interval
                val take = dp[nxt[i]][c + 1] + newIntervals[i][2]
                val tvec = choose[nxt[i]][c + 1].clone()
                tvec[3] = newIntervals[i][3] // Add current interval's original index
                tvec.sort()
                
                // Choose better option (or lexicographically smaller if equal)
                if (skip > take || (skip == take && compare(svec, tvec) < 0)) {
                    dp[i][c] = skip
                    choose[i][c] = svec
                } else {
                    dp[i][c] = take
                    choose[i][c] = tvec
                }
            }
        }
        
        // Extract result
        return choose[0][0].filter { it != INF }.toIntArray()
    }
    
    private fun compare(a: IntArray, b: IntArray): Int {
        for (i in 0 until 4) {
            if (a[i] != b[i]) {
                return a[i].compareTo(b[i])
            }
        }
        return 0
    }
}
 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()
##### Rust
 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

impl Solution {
    pub fn maximum_weight(mut intervals: Vec<Vec<i32>>) -> Vec<i32> {
        let n = intervals.len();
        
        // Add original indices to intervals
        for i in 0..n {
            intervals[i].push(i as i32);
        }
        
        // Sort by start time
        intervals.sort_by(|a, b| {
            a[0].cmp(&b[0])
                .then_with(|| a[1].cmp(&b[1]))
                .then_with(|| a[2].cmp(&b[2]))
        });
        
        // Precompute next non-overlapping interval for each interval
        let mut nxt = vec![0; n];
        for i in 0..n {
            let end = intervals[i][1];
            let mut l = 0;
            let mut r = n;
            while l < r {
                let m = (l + r) / 2;
                if intervals[m][0] > end {
                    r = m;
                } else {
                    l = m + 1;
                }
            }
            nxt[i] = l;
        }
        
        const INF: i32 = 1_000_000_000;
        let mut dp = vec![vec![0i64; 5]; n + 1];
        let mut choose = vec![vec![[INF; 4]; 5]; n + 1];
        
        // DP backwards
        for i in (0..n).rev() {
            for c in (0..=3).rev() {
                // Option 1: Skip current interval
                let skip = dp[i + 1][c];
                let svec = choose[i + 1][c];
                
                // Option 2: Take current interval
                let take = dp[nxt[i]][c + 1] + intervals[i][2] as i64;
                let mut tvec = choose[nxt[i]][c + 1];
                tvec[3] = intervals[i][3]; // Add current interval's original index
                tvec.sort();
                
                // Choose better option (or lexicographically smaller if equal)
                if skip > take || (skip == take && svec < tvec) {
                    dp[i][c] = skip;
                    choose[i][c] = svec;
                } else {
                    dp[i][c] = take;
                    choose[i][c] = tvec;
                }
            }
        }
        
        // Extract result
        choose[0][0]
            .iter()
            .filter(|&&id| id != INF)
            .copied()
            .collect()
    }
}
 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

function maximumWeight(intervals: number[][]): number[] {
    const n = intervals.length;
    
    // Add original indices to intervals
    const newIntervals: number[][] = intervals.map((interval, i) => [...interval, i]);
    
    // Sort by start time
    newIntervals.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        if (a[1] !== b[1]) return a[1] - b[1];
        return a[2] - b[2];
    });
    
    // Precompute next non-overlapping interval for each interval
    const nxt: number[] = new Array(n);
    for (let i = 0; i < n; i++) {
        const end = newIntervals[i][1];
        let l = 0, r = n;
        while (l < r) {
            const m = Math.floor((l + r) / 2);
            if (newIntervals[m][0] > end) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        nxt[i] = l;
    }
    
    const INF = 1e9;
    const dp: number[][] = Array(n + 1).fill(null).map(() => Array(5).fill(0));
    const choose: number[][][] = Array(n + 1).fill(null).map(() => 
        Array(5).fill(null).map(() => Array(4).fill(INF))
    );
    
    // DP backwards
    for (let i = n - 1; i >= 0; i--) {
        for (let c = 3; c >= 0; c--) {
            // Option 1: Skip current interval
            const skip = dp[i + 1][c];
            const svec = [...choose[i + 1][c]];
            
            // Option 2: Take current interval
            const take = dp[nxt[i]][c + 1] + newIntervals[i][2];
            const tvec = [...choose[nxt[i]][c + 1]];
            tvec[3] = newIntervals[i][3]; // Add current interval's original index
            tvec.sort((a, b) => a - b);
            
            // Choose better option (or lexicographically smaller if equal)
            if (skip > take || (skip === take && compare(svec, tvec) < 0)) {
                dp[i][c] = skip;
                choose[i][c] = svec;
            } else {
                dp[i][c] = take;
                choose[i][c] = tvec;
            }
        }
    }
    
    // Extract result
    return choose[0][0].filter(id => id !== INF);
}

function compare(a: number[], b: number[]): number {
    for (let i = 0; i < 4; i++) {
        if (a[i] !== b[i]) {
            return a[i] - b[i];
        }
    }
    return 0;
}

Complexity

  • ⏰ Time complexity: O(n log n), where n is the number of intervals. The sorting takes O(n log n) and the DP with binary search preprocessing takes O(n log n) total time.
  • 🧺 Space complexity: O(n), for the DP tables and index tracking arrays.ms