Score Selection: Find the K Highest Non-Overlapping Score Intervals

Question

## Problem

You are given a list of score intervals, each with a start index, end index, and a score value. Select up to `k` non-overlapping intervals to maximize total score. Two intervals overlap if they share any index.

```python
def max_score_selection(intervals: list[tuple[int, int, int]], k: int) -> int:
    # intervals[i] = (start, end, score)
    # return maximum total score using at most k non-overlapping intervals
    pass
```

**Example:**
```
intervals = [(0, 2, 10), (1, 4, 20), (3, 5, 15), (6, 8, 25)]
k = 2
Output: 35  # select (1,4,20) and (6,8,25)
```

## Approach

Sort by end index. Use DP where `dp[i][j]` = max score using `j` intervals from the first `i` candidates. Binary search for the last non-overlapping interval.

## Follow-ups

1. What is the time complexity of your DP solution? Can you do better?
2. How would you reconstruct which intervals were selected, not just the score?
3. If intervals can partially overlap with a penalty, how does the recurrence change?
4. Solve the unbounded variant: you can pick any number of non-overlapping intervals.

Score Selection: Find the K Highest Non-Overlapping Score Intervals

Question Details

Full Details

Topics

More from Uber