3414. Maximum Score of Non-overlapping Intervals

Description

You are given a 2D integer array intervals, where intervals[i] = [l_i, r_i, weight_i]. Interval i starts at position l_i and ends at r_i, and has a weight of weight_i. 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 * 10⁴
intervals[i].length == 3
intervals[i] = [l_i, r_i, weight_i]
1 <= l_i <= r_i <= 10⁹
1 <= weight_i <= 10⁹

Solutions

Solution 1

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;
    }
}

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];
    }
};

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]

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)
}

3414 - Maximum Score of Non-overlapping Intervals

3414. Maximum Score of Non-overlapping Intervals

Description

Solutions

Solution 1

All Problems

All Solutions

Welcome to Subscribe On Youtube

3414. Maximum Score of Non-overlapping Intervals

Description

Solutions

Solution 1

All Problems

All Solutions