Maximum Score of Non-overlapping Intervals

hard intervals dynamic programming binary search sorting

Problem

You are given intervals where intervals[i] = [l_i, r_i, weight_i]. Choose up to 4 intervals that are pairwise non-overlapping (two intervals overlap if they share any point, including a touching boundary) so the total weight is maximum. Return the lexicographically smallest array of at most 4 original indices that achieves this maximum score.

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

Output[2,3]

Indices 2 and 3 give weights 5 + 3 = 8; intervals [1,5] and [6,9] do not touch, and no allowed selection scores higher.

intervals (l:r:w, comma-separated)

def maximumWeight(intervals):
    n = len(intervals)
    # Sort positions by right boundary (tie: left boundary), keep original index.
    order = sorted(range(n), key=lambda i: (intervals[i][1], intervals[i][0]))
    L = [intervals[order[i]][0] for i in range(n)]
    R = [intervals[order[i]][1] for i in range(n)]
    W = [intervals[order[i]][2] for i in range(n)]
    orig = [order[i] for i in range(n)]

    def better(a, b):                       # higher score wins; tie -> smaller index list
        if a[0] != b[0]:
            return a if a[0] > b[0] else b
        return a if a[1] <= b[1] else b

    from bisect import bisect_left
    # dp[k][i] = best (score, sorted-index-tuple) using <= k intervals from prefix [0..i-1]
    dp = [[(0, ()) for _ in range(n + 1)] for _ in range(5)]
    for k in range(1, 5):
        for i in range(1, n + 1):
            p = i - 1
            best = dp[k][i - 1]             # option A: skip interval p
            j = bisect_left(R, L[p])        # count of intervals ending before L[p]
            prev = dp[k - 1][j]             # best with one fewer pick, non-overlapping
            cand = (prev[0] + W[p], tuple(sorted(prev[1] + (orig[p],))))
            dp[k][i] = better(best, cand)   # option B: take interval p
    return list(dp[4][n][1])

function maximumWeight(intervals) {
  const n = intervals.length;
  // Sort positions by right boundary (tie: left boundary), keep original index.
  const order = [...Array(n).keys()].sort((a, b) =>
    intervals[a][1] - intervals[b][1] || intervals[a][0] - intervals[b][0]);
  const L = order.map(o => intervals[o][0]);
  const R = order.map(o => intervals[o][1]);
  const W = order.map(o => intervals[o][2]);

  function better(a, b) {                  // higher score wins; tie -> smaller index list
    if (a.s !== b.s) return a.s > b.s ? a : b;
    return lexLE(a.idx, b.idx) ? a : b;
  }
  function lexLE(x, y) {                    // is x <= y lexicographically?
    for (let i = 0; i < Math.min(x.length, y.length); i++)
      if (x[i] !== y[i]) return x[i] < y[i];
    return x.length <= y.length;
  }
  function bisectLeft(arr, t) {            // first index with arr[index] >= t
    let lo = 0, hi = arr.length;
    while (lo < hi) { const m = (lo + hi) >> 1; if (arr[m] < t) lo = m + 1; else hi = m; }
    return lo;
  }
  // dp[k][i] = { s: score, idx: sorted index list } using <= k intervals from prefix [0..i-1]
  const dp = Array.from({ length: 5 }, () =>
    Array.from({ length: n + 1 }, () => ({ s: 0, idx: [] })));
  for (let k = 1; k <= 4; k++) {
    for (let i = 1; i <= n; i++) {
      const p = i - 1;
      let best = dp[k][i - 1];            // option A: skip interval p
      const j = bisectLeft(R, L[p]);      // count of intervals ending before L[p]
      const prev = dp[k - 1][j];          // best with one fewer pick, non-overlapping
      const cand = { s: prev.s + W[p], idx: [...prev.idx, order[p]].sort((a, b) => a - b) };
      dp[k][i] = better(best, cand);      // option B: take interval p
    }
  }
  return dp[4][n].idx;
}

int[] maximumWeight(List<List<Integer>> intervals) {
    int n = intervals.size();
    // Sort positions by right boundary (tie: left boundary), keep original index.
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> intervals.get(a).get(1).equals(intervals.get(b).get(1))
        ? intervals.get(a).get(0) - intervals.get(b).get(0)
        : intervals.get(a).get(1) - intervals.get(b).get(1));
    long[] L = new long[n], R = new long[n], W = new long[n];
    int[] orig = new int[n];
    for (int i = 0; i < n; i++) {
        L[i] = intervals.get(order[i]).get(0); R[i] = intervals.get(order[i]).get(1);
        W[i] = intervals.get(order[i]).get(2); orig[i] = order[i];
    }
    // dp[k][i] = best (score + sorted index list) using <= k intervals from prefix [0..i-1]
    State[][] dp = new State[5][n + 1];
    for (int k = 0; k <= 4; k++)
        for (int i = 0; i <= n; i++) dp[k][i] = new State(0, new int[0]);
    for (int k = 1; k <= 4; k++) {
        for (int i = 1; i <= n; i++) {
            int p = i - 1;
            State best = dp[k][i - 1];               // option A: skip interval p
            int j = bisectLeft(R, L[p]);             // count of intervals ending before L[p]
            State prev = dp[k - 1][j];               // best with one fewer pick
            int[] picked = append(prev.idx, orig[p]);
            dp[k][i] = better(best, new State(prev.score + W[p], picked));  // option B: take p
        }
    }
    return dp[4][n].idx;
}

vector<int> maximumWeight(vector<vector<int>>& intervals) {
    int n = intervals.size();
    // Sort positions by right boundary (tie: left boundary), keep original index.
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return intervals[a][1] != intervals[b][1]
            ? intervals[a][1] < intervals[b][1] : intervals[a][0] < intervals[b][0];
    });
    vector<long> L(n), R(n), W(n);
    vector<int> orig(n);
    for (int i = 0; i < n; i++) {
        L[i] = intervals[order[i]][0]; R[i] = intervals[order[i]][1];
        W[i] = intervals[order[i]][2]; orig[i] = order[i];
    }
    // dp[k][i] = best { score, sorted index list } using <= k intervals from prefix [0..i-1]
    State empty; empty.score = 0;
    vector<vector<State>> dp(5, vector<State>(n + 1, empty));
    for (int k = 1; k <= 4; k++) {
        for (int i = 1; i <= n; i++) {
            int p = i - 1;
            State best = dp[k][i - 1];               // option A: skip interval p
            int j = bisectLeft(R, L[p]);             // count of intervals ending before L[p]
            State prev = dp[k - 1][j];               // best with one fewer pick
            vector<int> picked = prev.idx; picked.push_back(orig[p]);
            sort(picked.begin(), picked.end());
            dp[k][i] = better(best, {prev.score + W[p], picked});  // option B: take p
        }
    }
    return dp[4][n].idx;
}

Explanation

We may keep at most 4 intervals and they must be pairwise non-overlapping (touching endpoints counts as overlap). Among all selections of maximum total weight, we want the one whose sorted list of original indices is lexicographically smallest.

First sort the intervals by their right boundary (breaking ties by left boundary), remembering each interval's original index. After sorting, the array R of right boundaries is increasing, which lets us binary-search for compatibility.

Let dp[k][i] be the best answer using at most k intervals chosen from the first i sorted intervals. For interval at sorted position p = i − 1 we have two choices. Skip it: the answer is dp[k][i − 1]. Take it: every previously chosen interval must end strictly before this one's left boundary L[p], so we find j = bisect_left(R, L[p]) — the number of intervals ending before L[p] — and extend dp[k − 1][j] with this interval.

Each dp entry stores both the score and the sorted tuple of original indices. We compare two entries with better: the larger score wins, and on a tie the lexicographically smaller index list wins. Carrying the index list through the recurrence yields the required tie-break automatically. The final answer is dp[4][n].

Because at most 4 intervals are picked and binary search is logarithmic, this runs in O(n log n) time after sorting, which comfortably handles up to 5·10⁴ intervals.

Time: O(n log n) Space: O(n)