381. Maximum Score of Non-overlapping Intervals
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.
Examples
Input: [[1,3,2],[4,5,2],[1,5,5],[6,9,3],[6,7,1],[8,9,1]]
Output: [2,3]
Explanation: Intervals 2 ([1,5] w=5) and 3 ([6,9] w=3) are non-overlapping and give the maximum score 8; [2,3] is the lexicographically smallest index list achieving it.
Constraints
- 1 <= intervals.length <= 5 * 10^4
- intervals[i].length == 3
- intervals[i] = [l_i, r_i, weight_i]
- 1 <= l_i <= r_i <= 10^9
- 1 <= weight_i <= 10^9
Run checks all cases above. Submit evaluates all test cases.