Sorted containers

You’ll recognise it when

• Items arrive one at a time, and after each one you need them in order, not just at the end.
• A query asks for the nearest key at or below a value, or at or above it: the latest price at or before time t, the closest free spot, the first server clockwise from a point.
• A new interval must not overlap the ones you already have: bookings, memory blocks, ranges that merge as numbers arrive.
• You need a player’s rank or the top k while scores keep changing.

A heap is the usual mix-up. It also stays ordered as items arrive, but it only shows you the smallest. If you need the neighbours of any value, or to delete any item, you need a sorted container.

The idea

Think of a paper diary. To check whether 2 pm to 3 pm is free, you don’t read the whole week. You find where 2 pm falls, then look at the appointment just before it and the one just after. If the one before ends by 2 and the one after starts at 3 or later, the slot is free. Nothing further away can get in the way.

A sorted container keeps keys in order while you add and remove them, so every “nearest” question becomes a binary search. The answer always sits right next to where the search lands:

• the floor of x is the largest key <= x;
• the ceiling of x is the smallest key >= x.

The strict versions, largest < x and smallest > x, are often called lower and higher.

The three languages differ a lot here. C++ and Java have balanced trees built in: std::set and std::map, TreeSet and TreeMap. Every search, insert and delete is O(log n). Python has no balanced tree in its standard library. The usual substitute is a plain list kept sorted with the bisect module: searching is O(log n), but inserting is O(n) because later items shift along. The third-party sortedcontainers.SortedList makes inserts fast too, but it’s often not available in interviews, and this site’s judge doesn’t have it either.

How it works

The example is a calendar that accepts a booking [start, end) only if it overlaps nothing already booked. Bookings are half-open, so one ending at 10 and one starting at 10 don’t clash.

Scroll through the steps and the graphic follows along. The top rows are the sorted container; the bottom is the same bookings on a timeline. Press edit to try your own bookings.

Why two neighbours are enough: accepted bookings never overlap, so every booking before the floor has ended by the time the floor starts, which is at or before start. Every booking after after starts even later than after does, so if after doesn’t reach into the new booking, nothing beyond it can.

import bisect


class Bookings:
    """Non-overlapping bookings [start, end)."""

    def __init__(self):
        self.starts = []   # sorted start times
        self.ends = []     # ends[j] goes with starts[j]

    def book(self, start, end):
        # starts[:i] <= start < starts[i:]
        i = bisect.bisect_right(self.starts, start)
        floor, after = i - 1, i

        # the last booking starting at or before `start`
        if floor >= 0 and self.ends[floor] > start:
            return False

        # the first booking starting after `start`
        n = len(self.starts)
        if after < n and self.starts[after] < end:
            return False

        self.starts.insert(i, start)
        self.ends.insert(i, end)
        return True

#include <map>
using namespace std;

// Non-overlapping bookings [start, end).
class Bookings {
    map<int, int> cal;   // start -> end, sorted by start

public:
    bool book(int start, int end) {
        // the first booking starting after `start`
        auto after = cal.upper_bound(start);

        // the one before it is the floor
        if (after != cal.begin()) {
            auto floor = prev(after);
            if (floor->second > start) {
                return false;
            }
        }

        if (after != cal.end() && after->first < end) {
            return false;
        }

        cal.emplace_hint(after, start, end);
        return true;
    }
};

import java.util.TreeMap;

// Non-overlapping bookings [start, end).
class Bookings {
    // start -> end, sorted by start
    TreeMap<Integer, Integer> cal = new TreeMap<>();

    boolean book(int start, int end) {
        // the last booking starting at or before `start`
        Integer floor = cal.floorKey(start);
        if (floor != null && cal.get(floor) > start) {
            return false;
        }

        // the first booking starting after `start`
        Integer after = cal.higherKey(start);
        if (after != null && after < end) {
            return false;
        }

        cal.put(start, end);
        return true;
    }
}

In C++ and Java the tree does the searching. upper_bound(start) and higherKey(start) find after directly, and the floor is prev(after) or floorKey(start). Here are the same lookups side by side:

std::map has the same lower_bound and upper_bound. TreeMap names them floorKey, ceilingKey and so on (or floorEntry to get the value too), with headMap and pollFirstEntry for the last two rows. Java’s headMap and tailMap are live views, not copies: removing a key through the view removes it from the map. To add in Python, bisect.insort(a, x) does the search and the insert in one call.

Why it’s O(log n)

std::map and TreeMap are balanced binary search trees (red-black trees in practice). They rebalance after every change, so their height stays at most about 2 log₂ n. A search, insert or delete walks one path from the root down, so each is O(log n).

A Python list is different. bisect is a binary search, so finding the spot is O(log n). But insert and pop(i) shift every later item one place, which is O(n). The shift is one fast block copy, so it’s fine in practice up to about 10⁵ inserts: that many inserts at random places take under a second, while 10⁶ take over a minute.

The last two rows are where the list wins. A tree has no indexes, so finding the k-th key means walking k steps. Space is O(n) either way.

Common mistakes

a[bisect_left(a, x) - 1]    # ✗ largest key < x
a[bisect_right(a, x) - 1]   # ✓ largest key <= x

i = bisect_right(a, x)
return a[i - 1]                       # ✗ i == 0 reads a[-1]
return a[i - 1] if i > 0 else None    # ✓

board[j] = (-new, name)                   # ✗ the list may be out of order now
board.pop(bisect_left(board, (-old, name)))
insort(board, (-new, name))               # ✓ remove, then insert

Variations

• Latest value at or before time t. Keep (time, value) pairs sorted by time and take the floor of t. If times only ever increase, appending keeps the list sorted, so only the lookup needs bisect.
• Leaderboards. Keep (-score, name) pairs in a sorted list. The top k are the first k items, and a player’s rank is bisect_left(board, (-score, name)) + 1. Negating the score puts the highest first, and equal scores fall back to name order.
• Merging ranges on insert. Keep disjoint ranges keyed by start. A new value or range can only touch its floor and its ceiling, so merge with those, and keep merging while the new range swallows the next one. A memory allocator does the same when a freed block joins its free neighbours.
• Wrap-around lookups. For points on a circle, like servers on a hash ring, take the ceiling, and if there is none, wrap round to the smallest key.
• Duplicates. C++ std::multiset keeps copies: s.erase(s.find(x)) removes one, while s.erase(x) removes them all. Java has no multiset, so use a TreeMap from key to count.