Maximum Coins From K Consecutive Bags

Read the statement literally: for every possible start position on the line, slide the length-k window there, add up the overlap with every segment, and remember the biggest total. It is guaranteed correct because it exhausts every window, but the number of starts is the coordinate span S (the largest bag that can hold coins), and recalculating every window from scratch repeats the overlaps it measured one step earlier.

class Solution:
    def maximumCoins(self, coins: list[list[int]], k: int) -> int:
        best = 0
        # S = the largest bag coordinate that can contain coins.
        farthest = max(r for _, r, _ in coins)
        for start in range(1, farthest + 1):
            end = start + k - 1
            total = 0
            for l, r, c in coins:
                # Overlap of the window [start, end] with bag span [l, r].
                lo = max(start, l)
                hi = min(end, r)
                if lo <= hi:
                    total += c * (hi - lo + 1)
            best = max(best, total)
        return best

Why it is unusable at scale: the coordinate span S can reach 10^9 bags and k can reach 10^9 independently, so up to 10^9 window starts each scan all N segments: O(S·N) time in O(1) space. Both dimensions are maxed out in the constraints precisely because the intended solution never walks the line coordinate by coordinate.

Sort the segments by left edge, then precompute prefix sums of each segment’s full coin total. A window query is then: find the contiguous run of segments the window intersects (two binary searches), take the prefix-sum range, and subtract the (at most two) overhangs — the first segment sticking past the window’s left edge and the last segment sticking past its right edge. The only starts worth querying are the candidate alignments: L = l_i and L = r_i − k + 1 for every segment.

from bisect import bisect_left, bisect_right

class Solution:
    def maximumCoins(self, coins: list[list[int]], k: int) -> int:
        # Segments never overlap, so once sorted a window only ever
        # intersects one contiguous run of segments.
        coins.sort()
        n = len(coins)
        lefts = [s[0] for s in coins]
        rights = [s[1] for s in coins]
        # Prefix sums of full segment totals: pref[i + 1] sums segments 0..i.
        pref = [0] * (n + 1)
        for i, (l, r, c) in enumerate(coins):
            pref[i + 1] = pref[i] + c * (r - l + 1)

        # A start L can only be optimal when a window edge aligns to a
        # segment edge: left edge on a segment start, or right edge on a
        # segment end (L = r - k + 1).
        starts = set()
        for l, r, _ in coins:
            starts.add(l)
            starts.add(max(1, r - k + 1))

        best = 0
        for L in starts:
            R = L + k - 1
            # Segments a..b intersect the window [L, R]:
            a = bisect_left(rights, L)      # first segment ending at or after L
            b = bisect_right(lefts, R) - 1  # last segment starting at or before R
            if a > b:
                continue                    # the window overlaps no segment
            total = pref[b + 1] - pref[a]
            if lefts[a] < L:                # segment a overhangs the left edge
                total -= coins[a][2] * (L - lefts[a])
            if rights[b] > R:               # segment b overhangs the right edge
                total -= coins[b][2] * (rights[b] - R)
            best = max(best, total)
        return best

Correctness sketch: fix k and slide L. Between two consecutive breakpoints of the form l_i or r_i − k + 1, every overlapping segment keeps the same clip pattern, so the window total is affine in L — its maximum on that run sits at one of the run’s two ends, both candidate starts by construction. Where the window crosses a segment start the total jumps upward exactly at L = l_i, another candidate. Therefore some optimal start is always in the candidate set.

Watch the mechanism — the candidate sweep on example 1. Note how the right-edge alignment at L = 3 takes the lead, and how the straight-line interior slides can never beat their own alignment ends:

Then example 2, a uniform segment that collapses the search into a flat plateau — the two candidate edges already prove the answer for every interior start:

Why it is O(N log N): the sort dominates the running time; after sorting, there are at most 2N candidates, and each one costs two O(log N) binary searches plus O(1) arithmetic — O(N log N) time in total. Space is O(N) for the lefts, rights, and pref arrays. Note the brute-force position span (up to 10^9) never appears anywhere in the algorithm: the number line is only ever touched at segment boundaries.