LeetCode Solutions Blog

Maximum Score of Non-overlapping Intervals

Number: 3562

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an array of intervals where each interval is represented as [l, r, weight] (with l and r defining the start and end positions, and weight being a positive integer), choose at most 4 intervals that do not overlap (note that even sharing a boundary counts as overlapping) so that the total weight is maximized. If there are multiple sets with the same maximum total weight, return the lexicographically smallest list of their original indices.

Key Insights

Since the number of intervals chosen is small (at most 4), a dynamic programming solution where the state includes the count of intervals selected is feasible.
Sorting intervals (for example, by their ending times) allows efficient binary search to find the previous non-overlapping interval.
Use binary search (or bisect) to quickly locate the rightmost interval whose end is strictly less than the current interval’s start.
DP state should capture both the maximum score and the chosen set (as a list of original indices) to later decide lexicographic order if scores are equal.
When combining solutions, always sort the candidate’s indices so that lexicographical comparison is done with their sorted order.

Space and Time Complexity

Time Complexity: O(4 * N * log N) where N is the number of intervals (binary search per DP update for 4 levels). Space Complexity: O(4 * N) storing DP states, each containing a score and list of indices.

Solution

We first sort the intervals by ending time while preserving their original indices. For each interval we can decide whether to take it or not, maintaining a DP table where dp[k][i] represents the best solution (maximum score and chosen index set) obtainable by considering the first i intervals and taking exactly k intervals.

To update dp[k][i], we have two choices:

Not picking the current interval, so dp[k][i] = dp[k][i-1].
Picking the current interval; then use binary search to find the rightmost interval j that ends strictly before the current interval’s start, and combine dp[k-1][j+1] with the current interval’s weight and original index.

When the candidate solutions have equal scores, we choose the one whose sorted list of indices is lexicographically smaller. Finally, since we can choose any number up to 4 intervals, we take the best among the DP solutions for 1, 2, 3, or 4 intervals.

Code Solutions

# Import bisect for binary search
import bisect

def max_non_overlapping_intervals(intervals):
    n = len(intervals)
    
    # Create a list of intervals augmented with their original index.
    # Each element: (l, r, weight, orig_index)
    intervals_aug = [(l, r, w, i) for i, (l, r, w) in enumerate(intervals)]
    # Sort intervals by end time to ease binary search;
    # note that overlapping conditions require r < current l (strict inequality)
    intervals_aug.sort(key=lambda x: x[1])
    
    # Precompute a list of end times for binary search
    ends = [interval[1] for interval in intervals_aug]
    
    # Maximum intervals allowed is 4. dp[k][i] will represent the best result (score, indices) 
    # using the first i intervals and selecting exactly k intervals.
    # Initialize dp as a 2D array with dimensions (5) x (n+1). 
    # We use k=0..4 (0 means selecting no interval).
    dp = [[(0, []) for _ in range(n+1)] for _ in range(5)]
    
    # dp[0][*] is (0, []) already.
    # Iterate for each number of intervals taken from 1 to 4.
    for k in range(1, 5):
        for i in range(1, n+1):
            # Current interval (from sorted order)
            l, r, w, orig_index = intervals_aug[i-1]
            
            # Option 1: don't take current interval, so copy answer from previous index.
            best_score, best_choice = dp[k][i-1]
            
            # Option 2: take current interval.
            # Find the rightmost interval in sorted order that ends strictly < current l.
            pos = bisect.bisect_left(ends, l) - 1
            # The previous best solution: if pos is -1, then choose no prior interval.
            prev_score, prev_choice = dp[k-1][pos+1]  # pos+1 works since dp indexes intervals processed.
            candidate_score = prev_score + w
            candidate_choice = prev_choice + [orig_index]
            candidate_choice.sort()  # ensure indices are sorted for lex order
            
            # Compare candidate solution with best from option 1.
            # First by score, then if equal, by lexicographic order of indices.
            if candidate_score > best_score:
                dp[k][i] = (candidate_score, candidate_choice)
            elif candidate_score == best_score:
                # Tie: choose lexicographically smaller array.
                if candidate_choice < best_choice:
                    dp[k][i] = (candidate_score, candidate_choice)
                else:
                    dp[k][i] = (best_score, best_choice)
            else:
                dp[k][i] = (best_score, best_choice)
    
    # Among dp[1..4][n], choose the best overall solution.
    best_total_score = 0
    best_indices = []
    for k in range(1, 5):
        score, indices = dp[k][n]
        if score > best_total_score:
            best_total_score = score
            best_indices = indices
        elif score == best_total_score:
            if indices < best_indices:
                best_indices = indices
    return best_indices

# Example usage:
if __name__ == "__main__":
    # Example 1:
    intervals1 = [[1,3,2],[4,5,2],[1,5,5],[6,9,3],[6,7,1],[8,9,1]]
    print(max_non_overlapping_intervals(intervals1))  # Expected output: [2,3]
    
    # Example 2:
    intervals2 = [[5,8,1],[6,7,7],[4,7,3],[9,10,6],[7,8,2],[11,14,3],[3,5,5]]
    print(max_non_overlapping_intervals(intervals2))  # Expected output: [1,3,5,6]