3414. Maximum Score of Non-overlapping Intervals LeetCode Solution
In this guide, you will get 3414. Maximum Score of Non-overlapping Intervals LeetCode Solution with the best time and space complexity. The solution to Maximum Score of Non-overlapping Intervals problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Score of Non-overlapping Intervals
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.
3414. Maximum Score of Non-overlapping Intervals LeetCode Solution in C++
struct T {
long weight;
vector<int> selected;
};
class Solution {
public:
vector<int> maximumWeight(vector<vector<int>>& input) {
vector<Interval> intervals;
for (int i = 0; i < input.size(); ++i)
intervals.emplace_back(input[i][0], input[i][1], input[i][2], i);
ranges::sort(intervals);
vector<vector<T>> memo(intervals.size(), vector<T>(5));
return dp(intervals, memo, 0, 4).selected;
}
private:
using Interval = tuple<int, int, int, int>;
T dp(const vector<Interval>& intervals, vector<vector<T>>& memo, int i,
int quota) {
if (i == intervals.size() || quota == 0)
return T();
if (memo[i][quota].weight > 0)
return memo[i][quota];
T skip = dp(intervals, memo, i + 1, quota);
auto [_, r, weight, originalIndex] = intervals[i];
const int j = findFirstGreater(intervals, i + 1, r);
T nextRes = dp(intervals, memo, j, quota - 1);
vector<int> newSelected = nextRes.selected;
newSelected.push_back(originalIndex);
ranges::sort(newSelected);
T pick(static_cast<long>(weight) + nextRes.weight, newSelected);
return memo[i][quota] =
(pick.weight > skip.weight ||
pick.weight == skip.weight && pick.selected < skip.selected)
? pick
: skip;
}
// Binary searches the first interval that starts after `rightBoundary`.
int findFirstGreater(const vector<Interval>& intervals, int startFrom,
int rightBoundary) {
int l = startFrom;
int r = intervals.size();
while (l < r) {
const int m = (l + r) / 2;
if (get<0>(intervals[m]) > rightBoundary)
r = m;
else
l = m + 1;
}
return l;
}
}; /* code provided by PROGIEZ */
3414. Maximum Score of Non-overlapping Intervals LeetCode Solution in Java
class Interval {
public int left;
public int right;
public int weight;
public int originalIndex;
public Interval(int left, int right, int weight, int originalIndex) {
this.left = left;
this.right = right;
this.weight = weight;
this.originalIndex = originalIndex;
}
}
class T {
public long weight;
public List<Integer> selected;
public T() {
this.weight = 0;
this.selected = new ArrayList<>();
}
public T(long weight, List<Integer> selected) {
this.weight = weight;
this.selected = selected;
}
}
class Solution {
public int[] maximumWeight(List<List<Integer>> intervals) {
// Convert input to Interval objects
List<Interval> indexedIntervals = new ArrayList<>();
for (int i = 0; i < intervals.size(); ++i) {
List<Integer> interval = intervals.get(i);
indexedIntervals.add(new Interval(interval.get(0), interval.get(1), interval.get(2), i));
}
indexedIntervals.sort((a, b) -> Integer.compare(a.left, b.left));
T[][] memo = new T[indexedIntervals.size()][5];
return dp(indexedIntervals, memo, 0, 4).selected.stream().mapToInt(Integer::intValue).toArray();
}
private T dp(List<Interval> intervals, T[][] memo, int i, int quota) {
if (i == intervals.size() || quota == 0)
return new T();
if (memo[i][quota] != null)
return memo[i][quota];
T skip = dp(intervals, memo, i + 1, quota);
Interval interval = intervals.get(i);
final int j = findFirstGreater(intervals, i + 1, interval.right);
T nextRes = dp(intervals, memo, j, quota - 1);
List<Integer> newSelected = new ArrayList<>(nextRes.selected);
newSelected.add(interval.originalIndex);
Collections.sort(newSelected);
T pick = new T(interval.weight + nextRes.weight, newSelected);
return memo[i][quota] =
(pick.weight > skip.weight ||
(pick.weight == skip.weight && compareLists(pick.selected, skip.selected) < 0))
? pick
: skip;
}
// Binary searches the first interval that starts after `rightBoundary`.
private int findFirstGreater(List<Interval> intervals, int startFrom, int rightBoundary) {
int l = startFrom;
int r = intervals.size();
while (l < r) {
final int m = (l + r) / 2;
if (intervals.get(m).left > rightBoundary)
r = m;
else
l = m + 1;
}
return l;
}
// Compares two lists of integers lexicographically.
private int compareLists(List<Integer> list1, List<Integer> list2) {
final int minSize = Math.min(list1.size(), list2.size());
for (int i = 0; i < minSize; ++i) {
final int comparison = Integer.compare(list1.get(i), list2.get(i));
if (comparison != 0)
return comparison;
}
return Integer.compare(list1.size(), list2.size());
}
} // code provided by PROGIEZ
3414. Maximum Score of Non-overlapping Intervals LeetCode Solution in Python
from dataclasses import dataclass
@dataclass(frozen=True)
class T:
weight: int
selected: tuple[int]
def __iter__(self):
yield self.weight
yield self.selected
class Solution:
def maximumWeight(self, intervals: list[list[int]]) -> list[int]:
intervals = sorted((*interval, i) for i, interval in enumerate(intervals))
@functools.lru_cache(None)
def dp(i: int, quota: int) -> T:
"""
Returns the maximum weight and the selected intervals for intervals[i..n),
where `quota` is the number of intervals that can be selected.
"""
if i == len(intervals) or quota == 0:
return T(0, ())
skip = dp(i + 1, quota)
_, r, weight, originalIndex = intervals[i]
j = bisect.bisect_right(intervals, (r, math.inf))
nextRes = dp(j, quota - 1)
pick = T(weight + nextRes.weight,
sorted((originalIndex, *nextRes.selected)))
return (pick if (pick.weight > skip.weight or
pick.weight == skip.weight and pick.selected < skip.selected)
else skip)
return list(dp(0, 4).selected) # code by PROGIEZ
