Show problems as
Classic problem #740MediumArrayHash TableDynamic Programming

Delete and Earn

Real-world version: Guard Band Licence Fees
Tracked in this browser only
Read Delete and Earn on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def guard_band_fees(requests: list[int]) -> int:
Java
public int guardBandFees(int[] requests)

More on the same topics