0203MediumArrayHash TableDynamic Programming

Guard Band Licence Fees

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A spectrum regulator is clearing a pile of licence applications for one radio band. requests holds one entry per application, and the entry is the channel number that application asks for. Several applications may ask for the same channel.

The regulator settles the pile one application at a time. Approving an application collects a fee equal to its channel number, and because a live transmitter spills into the slots on either side of it, approving an application for channel c immediately strikes out every application still in the pile asking for channel c - 1 and every one asking for channel c + 1. The approved application leaves the pile too. Any other application asking for channel c itself stays in the pile and may still be approved later.

The regulator repeats this until the pile is empty, so every application ends up either approved or struck out. Return the largest total fee the regulator can collect.

Examples

Example 1

Input: requests = [8, 9, 9, 12]
Output: 30

Approve one channel 9 application for a fee of 9, striking out the channel 8 one. The second channel 9 application and the channel 12 application still stand and are approved, giving 9 + 9 + 12 = 30.

Example 2

Input: requests = [6, 6, 3, 3, 1]
Output: 19

Channels 1, 3 and 6 are each more than one apart, so no approval strikes out anything and all five applications pay: 1 + 3 + 3 + 6 + 6 = 19.

Example 3

Input: requests = [5, 5, 5]
Output: 15

Approving a channel 5 application only strikes out applications for channels 4 and 6, of which there are none, so all three are approved for 5 + 5 + 5 = 15.

Example 4

Input: requests = [4, 4, 4, 5, 5, 5, 5, 6, 6]
Output: 24

Approve one channel 4 application: it pays 4 and strikes out all four channel 5 applications. The other two channel 4 applications and both channel 6 applications survive and are approved, giving 4 + 4 + 4 + 6 + 6 = 24.

Constraints

1 <= requests.length <= 2 * 10^4
1 <= requests[i] <= 10^4

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def guard_band_fees(requests: list[int]) -> int:

Java

public int guardBandFees(int[] requests)

The intended approach

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

Applications asking for the same channel never interfere with one another, so total the fees channel by channel and the pile collapses to one figure per distinct channel. Visit the distinct channels in ascending order carrying two running totals: the best fee assuming the channel just visited was approved, and the best assuming it was not. When the next channel is exactly one above the previous one, approving it has to build on the total that left the previous channel unapproved; when there is a wider gap, both running totals are available to build on.

Pythonentry point: guard_band_fees

def guard_band_fees(requests):
    # Time O(n log n): one pass to total the fees per channel, then the distinct
    # channels are sorted. Space O(n) for the per-channel totals.
    per_channel = {}
    for channel in requests:
        per_channel[channel] = per_channel.get(channel, 0) + channel
    granted = 0
    passed = 0
    previous = None
    for channel in sorted(per_channel):
        if previous is not None and channel == previous + 1:
            granted, passed = passed + per_channel[channel], max(granted, passed)
        else:
            base = max(granted, passed)
            granted, passed = base + per_channel[channel], base
        previous = channel
    return max(granted, passed)

The obvious version

Simulate the pile: try approving each remaining application in turn, strike out its neighbouring channels, and recurse on what is left, memoising on the sorted multiset of survivors. Exponential, exact for small piles.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_guard_band_fees(requests):
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def best(stack):
        if not stack:
            return 0
        top = 0
        for i, channel in enumerate(stack):
            rest = tuple(c for j, c in enumerate(stack)
                         if j != i and c != channel - 1 and c != channel + 1)
            total = channel + best(rest)
            if total > top:
                top = total
        return top

    return best(tuple(sorted(requests)))

How this problem was checked

Reference solution executed against 17 test cases — 17 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in