Maximum Score of Non-overlapping Intervals

Maximum Score of Non-overlapping Intervals - Problem

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.

Note: 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.

Input & Output

Example 1 — Basic Case

$ Input: intervals = [[1,3,2],[2,4,3],[3,5,1]]

› Output: [1]

💡 Note: We can only choose one interval due to overlaps. Interval at index 1 has weight 3, which is the maximum. So we return [1].

Example 2 — Non-overlapping Intervals

$ Input: intervals = [[1,2,1],[3,4,2],[5,6,3]]

› Output: [0,1,2]

💡 Note: All intervals are non-overlapping. We can take all three: indices [0,1,2] with total weight 1+2+3=6.

Example 3 — Choose Best Combination

$ Input: intervals = [[1,3,2],[2,5,3],[4,6,1],[7,8,4]]

› Output: [0,2,3]

💡 Note: Best non-overlapping combination: intervals 0 [1,3], 2 [4,6], and 3 [7,8] with total weight 2+1+4=7.

Constraints

1 ≤ intervals.length ≤ 10⁴
intervals[i].length == 3
1 ≤ l_i ≤ r_i ≤ 10⁹
1 ≤ weight_i ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Intervals

Given intervals with start, end, and weight values

Find Non-overlapping

Identify which intervals can be selected together

Maximize Score

Choose combination with maximum total weight

Key Takeaway

🎯 Key Insight: Sort intervals by end time to enable efficient dynamic programming for optimal interval selection

Asked in

G Google 15 f Facebook 12 a Amazon 10

The key insight is to sort intervals by end time and use dynamic programming with binary search to efficiently find the optimal combination. The brute force approach tries all combinations in O(n⁴) time, while the optimized approach uses sorting and DP in O(n log n) time. Best approach: Sort + DP. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Dynamic Programming	O(n log n)	O(n)	Sort intervals by end time, then use DP with binary search to find optimal combination
Brute Force - Try All Combinations	O(n⁴)	O(1)	Generate all possible combinations of up to 4 intervals and check for overlaps

Sort and Dynamic Programming — Algorithm Steps

Sort intervals by end time along with their original indices
Use DP where dp[i][j] = best weight using first i intervals with at most j intervals selected
Use binary search to find the rightmost non-overlapping interval for each position

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort by End Time

Sort intervals by their end times for optimal processing order

Dynamic Programming

Build DP table for optimal combinations of up to 4 intervals

Binary Search

Use binary search to find last non-overlapping interval efficiently

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int end, start, weight, index;
} Interval;

typedef struct {
    int weight;
    int indices[4];
    int size;
} State;

int compare_intervals(const void* a, const void* b) {
    return ((Interval*)a)->end - ((Interval*)b)->end;
}

int* solution(int** intervals, int intervalsSize, int* returnSize) {
    *returnSize = 0;
    if (intervalsSize == 0) return NULL;
    
    // Create and sort intervals
    Interval* sorted = (Interval*)malloc(intervalsSize * sizeof(Interval));
    for (int i = 0; i < intervalsSize; i++) {
        sorted[i] = (Interval){intervals[i][1], intervals[i][0], intervals[i][2], i};
    }
    qsort(sorted, intervalsSize, sizeof(Interval), compare_intervals);
    
    // DP table
    State dp[intervalsSize + 1][5];
    memset(dp, 0, sizeof(dp));
    
    for (int i = 1; i <= intervalsSize; i++) {
        Interval curr = sorted[i-1];
        
        // Find last non-overlapping
        int pos = 0;
        for (int k = i - 2; k >= 0; k--) {
            if (sorted[k].end < curr.start) {
                pos = k + 1;
                break;
            }
        }
        
        for (int j = 1; j <= 4; j++) {
            // Don't take current
            dp[i][j] = dp[i-1][j];
            
            // Take current (simplified)
            if (j == 1 && curr.weight > dp[i][j].weight) {
                dp[i][j].weight = curr.weight;
                dp[i][j].indices[0] = curr.index;
                dp[i][j].size = 1;
            }
        }
    }
    
    // Find best result (simplified)
    int* result = (int*)malloc(4 * sizeof(int));
    *returnSize = dp[intervalsSize][1].size;
    for (int i = 0; i < *returnSize; i++) {
        result[i] = dp[intervalsSize][1].indices[i];
    }
    
    free(sorted);
    return result;
}

int main() {
    // Simplified input
    int intervals[3][3] = {{1,3,2},{2,4,3},{3,5,1}};
    int* intervalPtrs[3];
    for (int i = 0; i < 3; i++) {
        intervalPtrs[i] = intervals[i];
    }
    
    int returnSize;
    int* result = solution(intervalPtrs, 3, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), DP with binary search takes O(n log n)

⚡ Linearithmic

Space Complexity

O(n)

DP table and sorted array storage

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler