LeetCode Entry

3414. Maximum Score of Non-overlapping Intervals

12.09.2026 hard 2026 kotlin rust

Max lexi-small pick of at most 4 intervals

3414. Maximum Score of Non-overlapping Intervals hard substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1480

Problem TLDR

Max lexi-small pick of at most 4 intervals

Intuition

DFS pick or skip, lookup for the next interval that is not intersecting the current. Compare sums and chosen indices.

Approach

• return pair of the sum and a list of indices

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

    fun maximumWeight(iv: List<List<Int>>) = run {
        val ii = iv.indices.sortedBy{iv[it][0]}; val dp = HashMap<Int, Pair<Long,List<Int>>>()
        fun dfs(i: Int, c: Int): Pair<Long,List<Int>> = if(c<4&&i<iv.size)dp.getOrPut(i*4+c) {
            var j = ii.binarySearch{j -> if(iv[ii[i]][1]<iv[j][0])1 else -1}.inv()
            val skip = dfs(i+1,c); val (ts,tp) = dfs(j,c+1)
            val ns = ts+1L*iv[ii[i]][2]; val np = (tp+ii[i]).sorted(); val take = ns to np
            val c = skip.second.zip(np).find{(a,b)->a!=b}?.let{(a,b)->a<=b}?:(skip.second.size<=np.size)
            if (skip.first>ns) skip else if (skip.first<ns) take else if (c) skip else take
        } else 0L to listOf<Int>()
        dfs(0, 0).second
    }