Maximum Score of Non-overlapping Intervals

Problem 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.

Key Insights

• You can select up to 4 intervals that do not overlap.
• The goal is to maximize the total weight while ensuring the selected intervals are non-overlapping.
• The output should be the indices of the selected intervals in lexicographical order.
• Sorting the intervals based on their end times can help in efficiently finding non-overlapping intervals.

Space and Time Complexity

Time Complexity: O(n log n) for sorting the intervals plus O(n) for dynamic programming or iteration. Thus, overall complexity is O(n log n). Space Complexity: O(n) for storing the intervals and possibly additional space for dynamic programming.

Solution

The solution can be approached using dynamic programming. We first sort the intervals based on their end times. Then, we iterate through each interval to determine the maximum score we can achieve by either including the current interval or excluding it. We can maintain a dynamic programming array that keeps track of the maximum score up to each interval. We also need a way to keep track of the indices of the selected intervals to ensure we return the lexicographically smallest array of indices.

1. Sort the intervals by their end times.
2. Use a dynamic programming array to keep track of the maximum weights.
3. For each interval, decide whether to include it based on the non-overlapping condition and update the maximum weight.
4. Keep track of the indices of selected intervals for the final output.

Code Solutions