Skip to content

3414. Maximum Score of Non-overlapping Intervals

SourceWeekly Contest 431 Q4DifficultyHardRating2723

Description

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:

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:

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 * 104
  • intervals[i].length == 3
  • intervals[i] = [li, ri, weighti]
  • 1 <= li <= ri <= 109
  • 1 <= weighti <= 109

Solutions

Solution 1: Sorting + Binary Search + Dynamic Programming

Thinking

We pick at most four non-overlapping weighted intervals to maximize the total weight, breaking ties by the lexicographically smallest index tuple. \(n\le 5\times 10^4\) forbids subset search.

This is weighted interval scheduling with a cap of four. After sorting by left endpoint, the next non-overlapping interval is a binary search.

State \((i,k)\) starts at interval \(i\) with \(k\) picks remaining. We either skip \(i\) or take it and jump to \(\textit{nxt}[i]\), comparing both weight and the index list so the lexicographically smallest optimum is kept.

Copy the intervals and record each original index, then sort by left endpoint. For each interval \(i\), binary-search the first position \(\textit{nxt}[i]\) whose left endpoint is strictly greater than \(i\)'s right endpoint (shared endpoints count as overlap).

Let \(f[i][k]\) be the maximum weight obtainable from interval \(i\) onward with at most \(k\) picks, and let \(g[i][k]\) store the corresponding lexicographically smallest index list. Transition from the back: skipping \(i\) inherits \(f[i+1][k]\); taking \(i\) inserts its original index into \(g[\textit{nxt}[i]][k-1]\) and adds the current weight. Keep the larger weight, or the lexicographically smaller index list on a tie. The answer is \(g[0][4]\).

The time complexity is \(O(n \times \log n)\) and the space complexity is \(O(n)\). At most \(4\) intervals are chosen, so inserting and comparing index lists is constant time.

 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
class Solution:
    def maximumWeight(self, intervals: List[List[int]]) -> List[int]:
        n = len(intervals)
        arr = [[e[0], e[1], e[2], i] for i, e in enumerate(intervals)]
        arr.sort()
        nxt = [0] * n
        for i in range(n):
            l, r = i + 1, n
            while l < r:
                mid = (l + r) >> 1
                if arr[mid][0] > arr[i][1]:
                    r = mid
                else:
                    l = mid + 1
            nxt[i] = l
        f = [[0] * 5 for _ in range(n + 1)]
        g = [[[] for _ in range(5)] for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            for k in range(1, 5):
                s1, a1 = f[i + 1][k], g[i + 1][k]
                a2 = g[nxt[i]][k - 1][:]
                x = arr[i][3]
                j = 0
                while j < len(a2) and a2[j] < x:
                    j += 1
                a2.insert(j, x)
                s2 = f[nxt[i]][k - 1] + arr[i][2]
                if s2 > s1 or (s2 == s1 and a2 < a1):
                    f[i][k] = s2
                    g[i][k] = a2
                else:
                    f[i][k] = s1
                    g[i][k] = a1
        return g[0][4]

 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
class Solution {
    public int[] maximumWeight(List<List<Integer>> intervals) {
        int n = intervals.size();
        int[][] arr = new int[n][4];
        for (int i = 0; i < n; ++i) {
            List<Integer> e = intervals.get(i);
            arr[i] = new int[] {e.get(0), e.get(1), e.get(2), i};
        }
        Arrays.sort(arr,
            (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
        int[] nxt = new int[n];
        for (int i = 0; i < n; ++i) {
            nxt[i] = search(arr, arr[i][1], i + 1);
        }
        long[][] f = new long[n + 1][5];
        int[][][] g = new int[n + 1][5][];
        for (int k = 0; k < 5; ++k) {
            g[n][k] = new int[0];
        }
        for (int i = n - 1; i >= 0; --i) {
            g[i][0] = new int[0];
            for (int k = 1; k < 5; ++k) {
                long s1 = f[i + 1][k];
                int[] a1 = g[i + 1][k];
                long s2 = f[nxt[i]][k - 1] + arr[i][2];
                int[] a2 = insert(g[nxt[i]][k - 1], arr[i][3]);
                if (s2 > s1 || (s2 == s1 && less(a2, a1))) {
                    f[i][k] = s2;
                    g[i][k] = a2;
                } else {
                    f[i][k] = s1;
                    g[i][k] = a1;
                }
            }
        }
        return g[0][4];
    }

    private int search(int[][] arr, int x, int l) {
        int r = arr.length;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (arr[mid][0] > x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    private int[] insert(int[] a, int x) {
        int n = a.length;
        int[] b = new int[n + 1];
        int i = 0;
        while (i < n && a[i] < x) {
            b[i] = a[i];
            ++i;
        }
        b[i] = x;
        while (i < n) {
            b[i + 1] = a[i];
            ++i;
        }
        return b;
    }

    private boolean less(int[] a, int[] b) {
        int m = Math.min(a.length, b.length);
        for (int i = 0; i < m; ++i) {
            if (a[i] != b[i]) {
                return a[i] < b[i];
            }
        }
        return a.length < b.length;
    }
}

 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
class Solution {
public:
    vector<int> maximumWeight(vector<vector<int>>& intervals) {
        int n = intervals.size();
        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};
        }
        ranges::sort(arr);
        vector<int> nxt(n);
        for (int i = 0; i < n; ++i) {
            int l = i + 1, r = n;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (arr[mid][0] > arr[i][1]) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            nxt[i] = l;
        }
        vector<vector<long long>> f(n + 1, vector<long long>(5));
        vector<vector<vector<int>>> g(n + 1, vector<vector<int>>(5));
        for (int i = n - 1; i >= 0; --i) {
            for (int k = 1; k < 5; ++k) {
                long long s1 = f[i + 1][k];
                vector<int> a1 = g[i + 1][k];
                long long s2 = f[nxt[i]][k - 1] + arr[i][2];
                vector<int> a2 = g[nxt[i]][k - 1];
                a2.insert(ranges::lower_bound(a2, arr[i][3]), arr[i][3]);
                if (s2 > s1 || (s2 == s1 && a2 < a1)) {
                    f[i][k] = s2;
                    g[i][k] = move(a2);
                } else {
                    f[i][k] = s1;
                    g[i][k] = move(a1);
                }
            }
        }
        return g[0][4];
    }
};

 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
func maximumWeight(intervals [][]int) []int {
    n := len(intervals)
    arr := make([][4]int, n)
    for i, e := range intervals {
        arr[i] = [4]int{e[0], e[1], e[2], i}
    }
    sort.Slice(arr, func(i, j int) bool {
        if arr[i][0] != arr[j][0] {
            return arr[i][0] < arr[j][0]
        }
        return arr[i][1] < arr[j][1]
    })
    nxt := make([]int, n)
    for i := 0; i < n; i++ {
        l, r := i+1, n
        for l < r {
            mid := (l + r) >> 1
            if arr[mid][0] > arr[i][1] {
                r = mid
            } else {
                l = mid + 1
            }
        }
        nxt[i] = l
    }
    f := make([][5]int64, n+1)
    g := make([][5][]int, n+1)
    for i := n - 1; i >= 0; i-- {
        for k := 1; k < 5; k++ {
            s1, a1 := f[i+1][k], g[i+1][k]
            a2 := append([]int(nil), g[nxt[i]][k-1]...)
            x := arr[i][3]
            j := sort.SearchInts(a2, x)
            a2 = append(a2, 0)
            copy(a2[j+1:], a2[j:])
            a2[j] = x
            s2 := f[nxt[i]][k-1] + int64(arr[i][2])
            if s2 > s1 || (s2 == s1 && lessInts(a2, a1)) {
                f[i][k] = s2
                g[i][k] = a2
            } else {
                f[i][k] = s1
                g[i][k] = a1
            }
        }
    }
    return g[0][4]
}

func lessInts(a, b []int) bool {
    m := min(len(a), len(b))
    for i := 0; i < m; i++ {
        if a[i] != b[i] {
            return a[i] < b[i]
        }
    }
    return len(a) < len(b)
}

Comments