Skip to main content
Talentd

Maximum Score of Non-overlapping Intervals - Solution & Explanation

HardArrayBinary SearchDynamic ProgrammingSorting7 min readAsked at: Amazon, Sprinklr
Practice this problem

Problem Statement

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.

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.

 

Example 1:

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

Output: [2,3]

Explanation:

You can choose the intervals with indices 2, and 3 with respective weights of 5, and 3.

Example 2:

Input: intervals = [[5,8,1],[6,7,7],[4,7,3],[9,10,6],[7,8,2],[11,14,3],[3,5,5]]

Output: [1,3,5,6]

Explanation:

You can choose the intervals with indices 1, 3, 5, and 6 with respective weights of 7, 6, 3, and 5.

 

Constraints:

  • 1 <= intevals.length <= 5 * 104
  • intervals[i].length == 3
  • intervals[i] = [li, ri, weighti]
  • 1 <= li <= ri <= 109
  • 1 <= weighti <= 109

Approach Overview

Problem Overview: You receive a list of intervals where each interval has a start time, end time, and score. The goal is to select a subset of non-overlapping intervals that maximizes the total score. If two intervals overlap in time, you can only choose one.

Approach 1: Brute Force Subset Enumeration (O(2^n) time, O(n) space)

The simplest idea is to generate every possible subset of intervals and check whether the chosen intervals overlap. For each valid subset, compute the total score and keep the maximum. Checking overlap requires sorting the chosen intervals and verifying adjacent ranges. This approach demonstrates the core constraint but becomes infeasible even for moderate n because the number of subsets grows exponentially.

Approach 2: Dynamic Programming with Sorting (O(n^2) time, O(n) space)

First sort intervals by their ending time. Define dp[i] as the maximum score achievable considering intervals up to index i. For each interval, iterate backward to find the latest interval that does not overlap. The recurrence becomes dp[i] = max(dp[i-1], score[i] + dp[prev]), where prev is the last compatible interval. This reduces the exponential search to polynomial time by reusing results. The idea mirrors classic weighted interval scheduling using dynamic programming.

Approach 3: DP + Binary Search (O(n log n) time, O(n) space)

Instead of scanning backward to locate the previous non-overlapping interval, store the sorted end times and use binary search. For each interval i, binary search the rightmost interval whose end time is less than or equal to the current start time. Combine its DP value with the current score. The recurrence remains the same, but the lookup becomes O(log n) rather than O(n). Sorting the intervals first using sorting ensures the DP state transitions are valid.

This approach scales well for large inputs. Each interval contributes a constant DP update and a binary search lookup.

Recommended for interviews: The DP with binary search solution is the expected approach. Starting from the brute force idea shows you understand the overlap constraint. Moving to sorted intervals and DP demonstrates the classic weighted scheduling optimization. Using binary search to locate the previous compatible interval reduces the complexity to O(n log n), which is the standard optimal solution interviewers look for.

Solution

Thinking

We pick at most four non-overlapping weighted intervals to maximize the total weight, breaking ties by the lexicographically smallest index tuple. n\le 5times 10^4 forbids subset search.

This is weighted interval scheduling with a cap of four. After sorting by left endpoint, the next non-overlapping interval is a binary search.

State (i,k) starts at interval i with k picks remaining. We either skip i or take it and jump to nxt[i], comparing both weight and the index list so the lexicographically smallest optimum is kept.

Copy the intervals and record each original index, then sort by left endpoint. For each interval i, binary-search the first position nxt[i] whose left endpoint is strictly greater than i's right endpoint (shared endpoints count as overlap).

Let f[i][k] be the maximum weight obtainable from interval i onward with at most k picks, and let g[i][k] store the corresponding lexicographically smallest index list. Transition from the back: skipping i inherits f[i+1][k]; taking i inserts its original index into g[nxt[i]][k-1] and adds the current weight. Keep the larger weight, or the lexicographically smaller index list on a tie. The answer is g[0][4].

The time complexity is O(n times log n) and the space complexity is O(n). At most 4 intervals are chosen, so inserting and comparing index lists is constant time.

Code

JavaC++

Java

C++

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subset EnumerationO(2^n)O(n)Conceptual understanding or very small input sizes
DP with Backward ScanO(n^2)O(n)Moderate input sizes where implementation simplicity matters
DP + Binary Search (Weighted Interval Scheduling)O(n log n)O(n)Optimal solution for large datasets and typical interview expectation

Video Solution

3414. Maximum Score of Non-overlapping Intervals (Leetcode Hard) • Programming Live with Larry • 679 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Maximum Score of Non-overlapping Intervals easy or hard?
Maximum Score of Non-overlapping Intervals is classified as Hard because it combines multiple concepts: sorting, binary search, and dynamic programming. Recognizing the connection to weighted interval scheduling and implementing the DP transition correctly is the main challenge.
Maximum Score of Non-overlapping Intervals Python/Java solution
Most implementations follow the same pattern: sort intervals by end time, precompute end-time arrays, then apply dynamic programming with binary search. This approach translates cleanly to Python, Java, C++, and Go using built-in sorting and binary search utilities.
How to solve Maximum Score of Non-overlapping Intervals in O(n log n)?
First sort intervals by their end time. Maintain a DP array where dp[i] stores the maximum score achievable considering intervals up to index i. For each interval, use binary search on the sorted end times to find the last interval that does not overlap, then update dp[i] using the recurrence max(dp[i-1], score[i] + dp[prev]).
What is the best approach for Maximum Score of Non-overlapping Intervals?
The best approach is dynamic programming combined with sorting and binary search. Sort intervals by end time, then compute a DP state where each entry represents the best score achievable up to that interval. Binary search finds the previous non-overlapping interval in O(log n), giving an overall time complexity of O(n log n).
Is Maximum Score of Non-overlapping Intervals asked at Google/Amazon/Meta?
Problems based on weighted interval scheduling frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often require selecting non-overlapping jobs, meetings, or tasks to maximize profit or score using dynamic programming and binary search.
What data structure is used in Maximum Score of Non-overlapping Intervals?
The solution primarily uses arrays or lists to store intervals and DP states. Binary search over a sorted array of end times is used to quickly locate the last compatible interval. The algorithm also relies on sorting and dynamic programming techniques.
What is the time complexity of Maximum Score of Non-overlapping Intervals?
The optimal solution runs in O(n log n) time. Sorting the intervals takes O(n log n), and each interval performs a binary search plus a constant-time DP update. Space complexity is O(n) for storing DP values and auxiliary arrays.

Ready to solve this problem?

Practice Maximum Score of Non-overlapping Intervals with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Best Non-Overlapping Events