LeetCode 3414 - Maximum Score of Non-overlapping Intervals

This problem combines weighted interval scheduling with an additional constraint: we may select at most 4 intervals, and if multiple selections achieve the same maximum total weight, we must return the lexicographically smallest list of original indices.

leetcodehardarraybinary-searchdynamic-programmingsorting

LeetCode Problem 3414

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Dynamic Programming, Sorting

Solution

Problem Understanding

This problem combines weighted interval scheduling with an additional constraint: we may select at most 4 intervals, and if multiple selections achieve the same maximum total weight, we must return the lexicographically smallest list of original indices.

Each interval is represented as:

[left, right, weight]

where:

  • left is the starting position
  • right is the ending position
  • weight is the score contributed by that interval

We may choose up to 4 intervals, provided they are non-overlapping.

The overlap definition is important. Two intervals are considered overlapping if they share any point. That means:

[1, 3] and [3, 5]

are overlapping because they both contain position 3.

Therefore, if we choose interval A ending at r, the next interval must start strictly after r.

The goal is not simply to maximize the number of intervals. We want to maximize the sum of weights. Among all solutions with maximum weight, we return the lexicographically smallest array of original indices.

For example:

[1, 4]

is lexicographically smaller than:

[1, 5]

because the first differing element is smaller.

Likewise:

[1, 3]

is lexicographically smaller than:

[1, 3, 7]

because when one array is a prefix of another, the shorter array is considered smaller.

The constraints are large:

n ≤ 50,000

A brute-force search over all subsets is completely impossible. We need something close to:

O(n log n)

or

O(n log n + nk)

where k = 4.

Some important edge cases are:

  • Only one interval exists.
  • The optimal solution uses fewer than 4 intervals.
  • Multiple interval sets produce the same total weight.
  • Many intervals overlap heavily.
  • Multiple solutions have identical weight and require lexicographical tie-breaking.
  • Large coordinate values up to 10^9, which prevent coordinate-based DP approaches. Let's carefully go step by step and create a full technical solution guide for LeetCode 3414 - Maximum Score of Non-overlapping Intervals.

Problem Understanding

The problem asks us to select up to four non-overlapping intervals from a given list of intervals, where each interval has a weight, such that the sum of the weights is maximized. Additionally, if multiple selections yield the same maximum score, we must return the lexicographically smallest array of indices of the chosen intervals.

Each interval is represented as [li, ri, weighti], meaning it starts at li and ends at ri inclusively, and has a weight weighti. Two intervals overlap if they share any point, including endpoints.

The input constraints indicate that the number of intervals can be very large (up to 50,000) and the range of positions (li and ri) and weights can go up to 10^9. This implies a brute-force approach that checks all possible combinations of intervals is infeasible.

Edge cases to consider upfront include:

  • Only one interval provided.
  • Multiple intervals completely overlapping.
  • Intervals with equal weights but different positions.
  • Intervals that exactly touch at boundaries (overlap by definition).

Approaches

Brute Force

A straightforward approach would be to examine every subset of intervals containing at most 4 elements.

For each subset we would:

  1. Verify that all chosen intervals are non-overlapping.
  2. Compute the total weight.
  3. Track the maximum score.
  4. Resolve ties using lexicographical comparison.

This approach is correct because it explicitly checks every possible valid selection.

Unfortunately, the number of subsets is enormous.

Even restricting ourselves to subsets of size at most 4 gives:

C(n,1) + C(n,2) + C(n,3) + C(n,4)

With n = 50,000, this is completely infeasible.

Optimal Approach

The key observation is that this is a weighted interval scheduling problem.

If we sort intervals by starting position, then for every interval we can quickly determine the next interval that does not overlap.

Suppose we choose interval i.

The next interval must satisfy:

start > end_i

Using binary search on sorted intervals, we can find the first valid interval index in O(log n) time.

Since we may select at most 4 intervals, the DP state is very small:

dp(i, remaining)

where:

  • i = current position in sorted intervals
  • remaining = how many intervals we may still take

At every state we have two choices:

  1. Skip interval i
  2. Take interval i

We choose whichever produces:

  • larger total weight
  • if weights tie, lexicographically smaller index list

Because the quota is only 4, storing the chosen indices inside the DP state is completely manageable.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n⁴) or worse O(1) Enumerates all possible interval combinations
Optimal O(n log n) O(n) DP + binary search with only 5 quota states

Algorithm Walkthrough

Step 1: Attach Original Indices

The answer must return indices from the original input.

Before sorting, augment each interval:

(left, right, weight, original_index)

Step 2: Sort Intervals

Sort intervals by starting position.

This allows binary searching for the next non-overlapping interval.

Example:

(start, end, weight, index)

becomes ordered by start.

Step 3: Define DP State

Let:

dp(i, quota)

represent:

(best_weight, chosen_indices)

using intervals from position i onward while still being allowed to select at most quota intervals.

Step 4: Handle Base Cases

If:

i == n

or

quota == 0

then no more intervals can be selected.

Return:

weight = 0
indices = []

Step 5: Compute the Skip Option

Ignore interval i.

Move to:

dp(i + 1, quota)

Step 6: Compute the Take Option

Suppose interval i is:

(l, r, w, originalIndex)

We need the first interval whose start position is strictly greater than r.

Using binary search:

j = first position with start > r

Then:

nextResult = dp(j, quota - 1)

and

takeWeight = w + nextResult.weight

The selected indices become:

[originalIndex] + nextResult.indices

Afterward we sort these indices because the problem wants the returned array ordered by index.

Step 7: Compare Take and Skip

If:

takeWeight > skipWeight

choose take.

If:

takeWeight < skipWeight

choose skip.

If weights tie:

choose lexicographically smaller index list

Step 8: Memoize Results

Store every computed state.

There are only:

n × 5

states.

Why it works

For every interval position we exhaustively consider the only two valid possibilities:

  • include the interval
  • exclude the interval

When including an interval, binary search jumps directly to the first interval that can legally follow it, ensuring all constructed solutions remain non-overlapping.

The DP explores every valid combination of up to four intervals exactly once. Since each state keeps the maximum achievable weight and resolves equal weights using lexicographical comparison, the final answer is guaranteed to be both weight-optimal and lexicographically minimal. A brute-force approach would try all combinations of up to 4 intervals, check if they are non-overlapping, calculate the total weight for each combination, and track the maximum.

While this is correct, the complexity is extremely high. For n intervals, the number of combinations of up to 4 intervals is $O(n^4)$. With n up to 50,000, this is computationally impossible.

Optimal Approach

The key insight is that we can sort intervals by end times and then use dynamic programming along with binary search to efficiently find the maximum weight of non-overlapping intervals.

The steps are:

  • Sort intervals by end time ri. This ensures that when we pick an interval, all potential non-overlapping candidates come before it.
  • Use DP to track the best weight achievable using 0, 1, 2, 3, or 4 intervals up to the current interval.
  • Use binary search to find the last interval that ends before the current interval starts (non-overlapping requirement).
  • Keep track of actual interval indices to ensure we can reconstruct the solution in lexicographically smallest order.

This reduces complexity dramatically because each interval is only considered in context of the previous bests, rather than all combinations.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^4) O(1) Check all combinations of up to 4 intervals
Optimal O(n log n) O(n) DP + binary search on sorted intervals

Algorithm Walkthrough

  1. Sort intervals by their ending points ri. This allows us to efficiently find non-overlapping candidates using binary search.

  2. Precompute a list of ends for binary search. This is an array of the end points of intervals, sorted by end time.

  3. Initialize a DP array where dp[k][i] represents the maximum weight achievable using k intervals from the first i intervals. Keep a parallel structure to store the selected indices.

  4. Iterate over each interval. For each interval i:

  5. For each k from 1 to 4:

  6. Use binary search to find the largest interval j whose end is less than the start of i.

  7. Compute dp[k][i] = max(dp[k][i-1], dp[k-1][j] + weight[i]).

  8. Update the selected indices accordingly to maintain lexicographically smallest sequence.

  9. After processing all intervals, the DP array contains the maximum achievable weight using up to 4 intervals. The stored indices give the required lexicographically smallest result.

Why it works: Sorting ensures non-overlapping candidates always appear before the current interval. DP maintains optimal solutions for 0-4 intervals, and binary search allows fast retrieval of compatible previous intervals. Lexicographical order is maintained by always comparing and keeping the smallest index sequence on ties.

Python Solution

from typing import List
from functools import lru_cache
from dataclasses import dataclass
from bisect import bisect_right
import math

@dataclass(frozen=True)
class State:
    weight: int
    indices: tuple

    def __iter__(self):
        yield self.weight
        yield self.indices

class Solution:
    def maximumWeight(self, intervals: List[List[int]]) -> List[int]:
        intervals = sorted(
            (l, r, w, i)
            for i, (l, r, w) in enumerate(intervals)
        )

        @lru_cache(None)
        def dp(i: int, quota: int) -> State:
            if i == len(intervals) or quota == 0:
                return State(0, ())

            skip = dp(i + 1, quota)

            _, r, weight, original_index = intervals[i]

            j = bisect_right(intervals, (r, math.inf))

            next_state = dp(j, quota - 1)

            take = State(
                weight + next_state.weight,
                tuple(sorted((original_index, *next_state.indices)))
            )

            if take.weight > skip.weight:
                return take

            if take.weight < skip.weight:
                return skip

            if take.indices < skip.indices:
                return take

            return skip

        return list(dp(0, 4).indices)

Implementation Explanation

The first step augments every interval with its original index and sorts the intervals by start position.

The memoized function dp(i, quota) returns a State object containing:

  • maximum obtainable weight
  • corresponding chosen indices

For each state we compute two possibilities.

The skip branch simply advances to the next interval.

The take branch uses bisect_right to find the first interval whose start value is strictly greater than the current interval's ending point. This satisfies the problem's strict non-overlap requirement.

After recursively computing the remainder of the solution, we add the current interval's weight and merge its index into the chosen set.

Finally, we compare the two candidates. Weight has higher priority. If weights are equal, Python's tuple comparison naturally performs lexicographical ordering.

Because the quota is only 4, the stored index tuples remain extremely small. from bisect import bisect_left from typing import List

class Solution: def maximumWeight(self, intervals: List[List[int]]) -> List[int]: n = len(intervals) indexed = [(l, r, w, i) for i, (l, r, w) in enumerate(intervals)] indexed.sort(key=lambda x: x[1]) # Sort by end

    ends = [r for _, r, _, _ in indexed]
    
    # dp[k][i] = (weight, indices) for best k intervals using first i intervals
    dp = [[(0, []) for _ in range(n+1)] for _ in range(5)]
    
    for i in range(1, n+1):
        l, r, w, idx = indexed[i-1]
        pos = bisect_left(ends, l)  # first end >= l
        prev = pos  # intervals ending before l are non-overlapping
        
        for k in range(1, 5):
            # Option 1: skip current interval
            option1 = dp[k][i-1]
            
            # Option 2: include current interval
            if prev > 0:
                weight2, indices2 = dp[k-1][prev]
            else:
                weight2, indices2 = 0, []
            option2 = (weight2 + w, indices2 + [idx])
            
            # Choose maximum weight, tie-break lexicographically
            if option1[0] > option2[0]:
                dp[k][i] = option1
            elif option1[0] < option2[0]:
                dp[k][i] = option2
            else:
                # tie in weight, choose lexicographically smaller
                dp[k][i] = min(option1, option2, key=lambda x: x[1])
    
    # Maximum over 1-4 intervals
    result = max((dp[k][n] for k in range(1,5)), key=lambda x: (x[0], [-i for i in x[1]]))
    return result[1]


**Explanation**:

The Python solution first sorts intervals by end time to enable binary search. It uses a DP table where `dp[k][i]` stores the best result using `k` intervals among the first `i`. For each interval and count `k`, it either skips the interval or includes it if it does not overlap, updating weights and indices while preserving lexicographical order.

## Go Solution

```go
package main

import (
	"math"
	"sort"
)

type State struct {
	weight int64
	ids    []int
}

func lessLex(a, b []int) bool {
	n := len(a)
	if len(b) < n {
		n = len(b)
	}

	for i := 0; i < n; i++ {
		if a[i] != b[i] {
			return a[i] < b[i]
		}
	}

	return len(a) < len(b)
}

func maximumWeight(intervals [][]int) []int {
	type Interval struct {
		l, r, w int
		idx     int
	}

	n := len(intervals)

	arr := make([]Interval, n)

	for i, v := range intervals {
		arr[i] = Interval{
			l:   v[0],
			r:   v[1],
			w:   v[2],
			idx: i,
		}
	}

	sort.Slice(arr, func(i, j int) bool {
		if arr[i].l != arr[j].l {
			return arr[i].l < arr[j].l
		}
		return arr[i].r < arr[j].r
	})

	memo := make([][]State, n+1)
	seen := make([][]bool, n+1)

	for i := range memo {
		memo[i] = make([]State, 5)
		seen[i] = make([]bool, 5)
	}

	var dp func(int, int) State

	dp = func(i int, quota int) State {
		if i == n || quota == 0 {
			return State{
				weight: 0,
				ids:    []int{},
			}
		}

		if seen[i][quota] {
			return memo[i][quota]
		}

		seen[i][quota] = true

		skip := dp(i+1, quota)

		j := sort.Search(n, func(k int) bool {
			return arr[k].l > arr[i].r
		})

		next := dp(j, quota-1)

		ids := make([]int, 0, len(next.ids)+1)
		ids = append(ids, arr[i].idx)
		ids = append(ids, next.ids...)
		sort.Ints(ids)

		take := State{
			weight: int64(arr[i].w) + next.weight,
			ids:    ids,
		}

		var result State

		if take.weight > skip.weight {
			result = take
		} else if take.weight < skip.weight {
			result = skip
		} else {
			if lessLex(take.ids, skip.ids) {
				result = take
			} else {
				result = skip
			}
		}

		memo[i][quota] = result
		return result
	}

	return dp(0, 4).ids
}

func main() {
	_ = math.MaxInt
}

Go-Specific Notes

The total weight can reach:

4 × 10^9

which exceeds a signed 32-bit integer.

Therefore the implementation stores weights using:

int64

The memoization table uses a separate seen matrix because a zero-weight state is a valid result and cannot be used as an uninitialized marker.

Lexicographical comparison is implemented manually through the lessLex helper.

Worked Examples

Example 1

Input:

[[1,3,2],
 [4,5,2],
 [1,5,5],
 [6,9,3],
 [6,7,1],
 [8,9,1]]

After attaching indices:

Interval Original Index
[1,3,2] 0
[4,5,2] 1
[1,5,5] 2
[6,9,3] 3
[6,7,1] 4
[8,9,1] 5

Sorted order:

Position Interval
0 (1,3,2,0)
1 (1,5,5,2)
2 (4,5,2,1)
3 (6,7,1,4)
4 (6,9,3,3)
5 (8,9,1,5)

Consider interval at position 1:

(1,5,5,index=2)

Binary search finds the first interval with:

start > 5

which is position 3.

Taking interval 2 yields:

weight = 5

plus the best result from position 3.

The best continuation is interval 3:

(6,9,3,index=3)

Total:

5 + 3 = 8

Indices:

[2,3]

No other valid combination exceeds weight 8.

Output:

[2,3]

Example 2

Input:

[[5,8,1],
 [6,7,7],
 [4,7,3],
 [9,10,6],
 [7,8,2],
 [11,14,3],
 [3,5,5]]

The optimal chain is:

Index Weight
6 5
1 7
3 6
5 3

Total:

5 + 7 + 6 + 3 = 21

After lexicographical ordering of indices:

[1,3,5,6]

No other valid selection achieves a larger weight.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting plus one binary search per DP state
Space O(n) Memoization for n × 5 states

The sorting phase costs:

O(n log n)

There are at most:

5n

DP states because the quota ranges from 0 to 4.

Each state performs one binary search costing:

O(log n)

Therefore the total complexity is:

O(n log n)

The memoized state count is linear, giving:

O(n)

space usage.

Test Cases

sol = Solution()

assert sol.maximumWeight(
    [[1,3,2],[4,5,2],[1,5,5],[6,9,3],[6,7,1],[8,9,1]]
) == [2,3]  # example 1

assert sol.maximumWeight(
    [[5,8,1],[6,7,7],[4,7,3],[9,10,6],[7,8,2],[11,14,3],[3,5,5]]
) == [1,3,5,6]  # example 2

assert sol.maximumWeight(
    [[1,1,10]]
) == [0]  # single interval

assert sol.maximumWeight(
    [[1,5,10],[2,6,20]]
) == [1]  # choose heavier overlapping interval

assert sol.maximumWeight(
    [[1,2,5],[3,4,5]]
) == [0,1]  # two non-overlapping intervals

assert sol.maximumWeight(
    [[1,2,5],[2,3,100]]
) == [1]  # touching intervals overlap

assert sol.maximumWeight(
    [[1,2,5],[4,5,5],[7,8,5],[10,11,5],[13,14,5]]
) == [0,1,2,3]  # can only choose up to four intervals

assert sol.maximumWeight(
    [[1,2,10],[4,5,10]]
) == [0,1]  # exact tie-free optimal solution

assert sol.maximumWeight(
    [[1,2,5],[4,5,5],[1,5,10]]
) == [0,1]  # equal weight, lexicographically smaller

assert sol.maximumWeight(
    [[1,100,1000],[101,200,1000],[201,300,1000],[301,400,1000]]
) == [0,1,2,3]  # large coordinates

Test Summary

Test Why
Example 1 Verifies basic weighted scheduling
Example 2 Verifies selection of four intervals
Single interval Smallest input size
Fully overlapping pair Must choose larger weight
Two disjoint intervals Basic non-overlap case
Shared boundary Confirms touching intervals overlap
Five disjoint intervals Enforces maximum of four selections
Simple optimal chain Standard DP behavior
Equal-weight tie Tests lexicographical ordering
Large coordinates Confirms no coordinate compression assumptions

Edge Cases

Intervals Sharing a Boundary

A common bug is treating intervals as non-overlapping when:

end == nextStart

For this problem they still overlap because they share a point.

For example:

[1,2]
[2,3]

cannot both be selected.

The implementation handles this correctly by binary searching for:

start > currentEnd

rather than:

start >= currentEnd

Multiple Solutions With Equal Weight

Two different interval selections may produce the same total score.

For example:

[0,1]

and

[0,2]

might both yield weight 10.

The problem requires the lexicographically smallest answer. The DP state stores both weight and selected indices, allowing exact tie-breaking whenever equal-weight solutions appear.

Fewer Than Four Intervals Are Optimal

The statement says "up to 4 intervals", not "exactly 4 intervals".

Sometimes selecting fewer intervals gives the maximum score.

Example:

[[1,10,100]]

The correct answer is simply:

[0]

The DP naturally handles this because it always compares taking and skipping intervals and never forces the quota to be fully used.

Large Weights

Each interval weight can be as large as:

10^9

and up to four intervals may be selected.

The total score can therefore reach:

4 × 10^9

The Go implementation uses int64 for safety, preventing overflow on systems where int may be 32-bit. import ( "sort" )

func maximumWeight(intervals [][]int) []int { n := len(intervals) type interval struct { l, r, w, idx int } arr := make([]interval, n) for i, v := range intervals { arr[i] = interval{v[0], v[1], v[2], i} } sort.Slice(arr, func(i, j int) bool { return arr[i].r < arr[j].r })

ends := make([]int, n)
for i := range arr {
    ends[i] = arr[i].r
}

dp := make([][][2]interface{}, 5) // dp[k][i] = (weight int, indices []int)
for k := 0; k < 5; k++ {
    dp[k] = make([][2]interface{}, n+1)
    for i := 0; i <= n; i++ {
        dp[k][i] = [2]interface{}{0, []int{}}
    }
}

for i := 1; i <= n; i++ {
    l, r, w, idx := arr[i-1].l, arr[i-1].r, arr[i-1].w, arr[i-1].idx
    pos := sort.Search(len(ends), func(j int) bool { return ends[j] >= l })
    prev := pos

    for k := 1; k <= 4; k++ {
        option1 := dp[k][i-1]
        weight2 := 0
        indices2 := []int{}
        if prev > 0 {
            weight2 = dp[k-1][prev][0].(int)
            indices2 = dp[k-1][prev][1].([]int)
        }
        option2 := [2]interface{}{weight2 + w, append(append([]int{}, indices2...), idx)}

        w1 := option1[0].(int)
        w2 := option2[0].(int)
        if w1 > w2 {
            dp[k][i] = option1
        } else if w1 < w2 {
            dp[k][i] = option2
        } else {
            lex1 := option1[1].([]int)
            lex2 := option2[1].([]int)
            smaller := lex1
            for j := 0; j < len(lex1) && j < len(lex2); j++ {
                if lex1[j] != lex2[j] {
                    if lex1[j] > lex2[j] {
                        smaller = lex2
                    }
                    break
                }
            }