Spectrum licence ledger

The regulator licenses slices of radio spectrum, hands slices back, and gets asked whether a whole band is licensed. Storing every kilohertz is not an option.

The problem

A licence covers a half-open band of frequencies [lo, hi) in kilohertz: lo is licensed, hi is not. Bands that meet end to end are one continuous licence — [10, 20) and [20, 30) together license everything from 10 up to 30.

Process a list of commands against a ledger that starts empty.

• grant lo hi — add [lo, hi) to the licensed set.
• revoke lo hi — remove [lo, hi) from the licensed set.
• check lo hi — is every frequency in [lo, hi) licensed right now?

Return the answers to the check commands, in order.

Input. commands — a list of [op, lo, hi], where op is "grant", "revoke" or "check", and lo < hi.

Output. A list of booleans, one per check.

Example.

[["grant", 100, 400], ["revoke", 200, 250],
 ["check", 150, 200], ["check", 150, 260]]   ->  [True, False]

After the revocation the ledger holds [100, 200) and [250, 400). The band 150–200 sits inside the first, so it is licensed. The band 150–260 crosses the hole at 200–250, so it is not.

A second example, where the boundary decides both answers:

[["grant", 10, 20], ["grant", 20, 30],
 ["check", 12, 28], ["check", 12, 31]]        ->  [True, False]

The two grants meet at 20 and become one licence [10, 30), so 12–28 is covered. 12–31 asks for frequency 30, which is above the licence, so it is not.

Constraints.

• 1 <= len(commands) <= 10^4
• 1 <= lo < hi <= 10^9
• the ledger starts empty

Hints

Approach

Brute force

Hold the licensed frequencies in a set of integers. A command over a band of 10⁹ kilohertz touches 10⁹ entries, and 10⁴ commands make 10¹³ operations against a set that would need gigabytes.

The insight

Store the licensed set as a sorted list of disjoint bands that never touch, and every command is a binary search plus the handful of bands it actually destroys.

Normalising the ledger — sorted, disjoint, no two abutting — is what makes the binary search meaningful. Each command then works on a contiguous run: once a band starts beyond the command's hi, so does every band after it. It also collapses check to one test, because if any band covers [lo, hi) it is the last one starting at or before lo. The list stays short: a grant leaves one band where several stood and a revoke adds at most one, so m commands leave at most m bands.

Algorithm

1. Keep ledger, a list of [lo, hi) bands sorted by lo, disjoint and non-touching.
2. grant: bisect for the first band starting at or after lo, step back one if the band before it ends at or after lo, absorb every band starting at or before hi into one widened band, splice it in.
3. revoke: bisect the same way, step back only if the previous band ends strictly after lo, then rebuild each overlapped band as the parts left of lo and right of hi.
4. check: bisect for the last band starting at or before lo, and answer whether its end reaches hi.

Complexity

Time O(m log m) amortised over m commands — each does one binary search plus the bands it removes, and every band is created once and removed once. Space O(m) for the ledger.

Solution

"""Spectrum licence ledger — disjoint ranges kept sorted, reached by bisect."""

import bisect


def grant(ledger, lo, hi):
    i = bisect.bisect_left(ledger, [lo])
    # A band ending exactly at lo abuts the new one, so it must be swallowed
    # too: the ledger never holds two ranges that touch.
    if i > 0 and ledger[i - 1][1] >= lo:
        i -= 1
    j = i
    while j < len(ledger) and ledger[j][0] <= hi:
        lo = min(lo, ledger[j][0])
        hi = max(hi, ledger[j][1])
        j += 1
    ledger[i:j] = [[lo, hi]]


def revoke(ledger, lo, hi):
    i = bisect.bisect_left(ledger, [lo])
    # Here abutting is not overlapping: a band ending exactly at lo loses
    # nothing, so only a strictly greater end reaches back.
    if i > 0 and ledger[i - 1][1] > lo:
        i -= 1
    kept = []
    j = i
    while j < len(ledger) and ledger[j][0] < hi:
        band_lo, band_hi = ledger[j]
        if band_lo < lo:
            kept.append([band_lo, lo])
        if band_hi > hi:
            kept.append([hi, band_hi])       # a cut through the middle leaves two
        j += 1
    ledger[i:j] = kept


def covered(ledger, lo, hi):
    # The last band starting at or before lo is the only one that can hold the
    # whole query, because the bands are disjoint and never touch.
    i = bisect.bisect_left(ledger, [lo + 1]) - 1
    return i >= 0 and ledger[i][1] >= hi


def solve(commands):
    ledger = []
    answers = []
    for op, lo, hi in commands:
        if op == 'grant':
            grant(ledger, lo, hi)
        elif op == 'revoke':
            revoke(ledger, lo, hi)
        else:
            answers.append(covered(ledger, lo, hi))
    return answers

TESTS = [
    (([['grant', 100, 400], ['revoke', 200, 250],
       ['check', 150, 200], ['check', 150, 260]],), [True, False]),
    (([['grant', 10, 20], ['grant', 20, 30],
       ['check', 12, 28], ['check', 12, 31]],), [True, False]),
    (([['check', 1, 2]],), [False]),
    (([['grant', 5, 9], ['revoke', 5, 9], ['check', 5, 6]],), [False]),
    (([['grant', 1, 1000000000], ['check', 1, 1000000000],
       ['revoke', 500, 501], ['check', 1, 1000000000],
       ['check', 501, 1000000000]],), [True, False, True]),
    (([['grant', 40, 50], ['grant', 10, 20], ['grant', 20, 40],
       ['check', 10, 50], ['revoke', 25, 26], ['check', 10, 50],
       ['check', 26, 50]],), [True, False, True]),
]

Pitfalls

• Merging only bands that strictly overlap on a grant leaves [10, 20) and [20, 30) as separate rows, so the check on 12–28 finds a band ending at 20 and answers False even though every frequency is licensed.
• Using that same >= test on a revoke reaches back into a band that ends exactly at lo and has nothing to lose, so the splice rewrites a band the command never touched.
• Forgetting that a revoke can split one band into two silently deletes the upper piece: revoking 500–501 from [1, 10^9) must leave [501, 10^9).
• Treating the bands as closed makes check 200 250 on the first example answer True, because the ends 200 and 250 look licensed while everything between them is not.

Variants

• Roadworks calendar — one grant against a ledger that is already sorted, without the revocations.
• Rehearsal room clashes — the same disjointness requirement, reached by dropping intervals instead.