Choose Up to Four Non-overlapping Intervals
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
You are given `intervals`, where `intervals[i] = [l_i, r_i, weight_i]` describes a closed interval from `l_i` to `r_i` and its positive weight.
Choose at most four pairwise non-overlapping intervals to maximize the sum of their weights. Intervals that share an endpoint overlap: for example, `[1,3]` and `[3,5]` cannot both be chosen.
Return the original, zero-based indices of the chosen intervals in increasing order. If several choices have the maximum weight, return the lexicographically smallest index array. At the first differing position, the array with the smaller index is smaller; if one array is a prefix of another, the shorter array is smaller.
### C++ Interface
```cpp
class Solution {
public:
vector<int> maximumWeight(vector<vector<int>>& intervals) {
}
};
```
### Examples
**Example 1**
```text
Input: intervals = [[4,4,5],[1,2,4],[3,5,9],[6,7,2]]
Output: [1,2,3]
```
Indices `[1,2,3]` select `[1,2]`, `[3,5]`, and `[6,7]`, which are pairwise disjoint and have total weight `4 + 9 + 2 = 15`. Interval `0` overlaps interval `2`, so they cannot both be chosen. The best selection excluding interval `2` has weight only `11`; including interval `2` permits both `1` and `3`, giving the unique maximum `15`. The returned indices refer to the original input order.
**Example 2**
```text
Input: intervals = [[1,2,8],[2,3,9],[4,4,1]]
Output: [1,2]
```
The first two intervals share endpoint `2`, so they overlap. Choosing indices `1` and `2` gives weight `10`, exceeding the weight `9` of indices `0` and `2`.
### Constraints
- `1 <= intervals.length <= 50000`.
- Each `intervals[i]` contains exactly three integers: `[l_i, r_i, weight_i]`.
- `1 <= l_i <= r_i <= 1000000000`.
- `1 <= weight_i <= 1000000000`.
### Clarifying Questions
- Does “at most four” allow fewer intervals? Yes; a choice with fewer intervals may have a larger total weight.
- Are the input intervals already ordered or distinct? Neither property is promised. Their original indices identify them.
- Is any maximum-weight choice acceptable? No. The lexicographic tie-break selects one index array.
### What a Strong Answer Covers
- The distinction between sharing an endpoint and being disjoint.
- The four-interval limit, original indices, and the full tie-breaking rule.
- Correct behavior for a single interval, equal-score choices, and large weight totals.
- A justification of optimality and resource bounds at the maximum input size.
### Follow-up Questions
- If several intervals have identical endpoints and weights, which original indices should the returned answer favor?
- How would the interface and resource bounds change if the selection limit were an additional input instead of four?
```hint Keep the full tie-break
Sort a working copy by right endpoint. A dynamic-programming state can keep both a score and its increasing index list. For an exact selection count, consider skipping an interval or combining it with compatible earlier intervals; use strictly smaller right endpoints for compatibility.
```
Overview: Choose at most four nonoverlapping weighted intervals and return the lexicographically smallest optimal set of original indices. Preserve strict endpoint compatibility and large weight totals.
