Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 63 ยท Search and Greedy Thinking

Sorting, Events and Sweeps

Use sorting as a contest weapon: custom keys, two-criteria orders, cmp_to_key, coordinate compression and sweep lines over events with correct tie-breaking.

Sorting is the quietest hero of competitive programming. Many hard-looking problems turn easy after one sort: the pairs line up, the intervals can be scanned left to right, and a greedy rule becomes obvious. Three skills cover most uses. You choose the right sort key, you shrink huge coordinates down to small indexes (coordinate compression), and you process things in order of time with a sweep line over events.

Python makes the first part pleasant, because sorted is stable, takes a key function, and compares tuples element by element. The classic algorithms behind sorting are covered in Sorting Basics; here we focus on how to use it as a tool.

Custom keys and two criteria

A key returns a value (often a tuple) that Python compares instead of the item itself. For "highest score first, then name alphabetically", negate the number that should go descending:

  • Numbers: negate them, as in -score.
  • Strings: you cannot negate them, so sort in two passes instead and rely on stability.

Stable means equal items keep their original relative order. That lets you sort by the less important criterion first and the most important criterion last. reverse=True also preserves the order of equal elements, so this works too.

Sometimes the order is defined by comparing two items, not by a key. The classic example: given numbers like 3, 30, 34, 5, 9, arrange them so that joining them gives the largest number. Item a goes before b when a + b (as text) is larger than b + a. For this, functools.cmp_to_key turns a comparison function into a key.

Python Keys, stability and cmp_to_key

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two habits are worth keeping. Sort indexes when you need to remember positions, as the last example shows. And avoid cmp_to_key when a plain key works, because it is several times slower on big inputs.

Coordinate compression

Imagine segments on a line with endpoints up to 10^9. You cannot make an array of size 10^9, but you only care about the relative order of the at most 2n distinct endpoints. Coordinate compression replaces each distinct value by its rank among the sorted distinct values. Everything that depends only on order, such as overlaps, counts and nesting, is unchanged, and now the coordinates are small enough to index arrays.

Python
xs = sorted(set(values))          # the distinct values in order
rank = {x: i for i, x in enumerate(xs)}

A very common use is the difference array on compressed points. Add +1 where a segment starts and -1 where it ends, then take running sums. Between two neighboring compressed points the coverage is constant, so each gap contributes gap_length if it is covered.

Python Union length of huge segments

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The array has only as many entries as there are distinct endpoints, regardless of how large the coordinates are. When you also need to answer queries about original values, keep xs and use bisect_left(xs, value) to map a value to its rank.

Sweep line over events

A sweep line imagines a vertical line moving across the plane (or time moving forward) and handles events in order. Each interval becomes two events, a start and an end. You sort all events and keep a running state, such as the number of currently active intervals.

flowchart LR
    A["Turn each interval into start and end events"] --> B["Sort events by time, then by type"]
    B --> C["Scan events in order"]
    C --> D["Update the running state"]
    D --> E["Record the answer after each event"]

A sweep line is a sort followed by a single scan.

The part that trips people up is ties: what happens when one meeting ends at time 3 and another starts at time 3? With half-open intervals [start, end), the first meeting is already over, so the room is free. To get this right, process the end events before start events at the same time. If you store events as (time, delta) with delta -1 for an end and +1 for a start, the plain tuple sort does exactly that, because -1 sorts before +1.

If the statement uses closed intervals, where touching intervals do overlap, you want the opposite order.

Python Busiest moment of a sweep

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The state can be richer than a counter: a sum of weights (for "maximum total value at one moment"), a set of active items, or a heap of end times. The structure stays the same: build events, sort, scan.

Putting the tools together

When a problem mentions intervals, queries over ranges, or "at the same time", reach for this sequence:

  1. Decide what an event is and how ties should break.
  2. Compress coordinates if they are large and only order matters.
  3. Sort once, then scan with an O(1) or O(log n) update per event.
  4. Check the tie rule with a two-element example before coding anything else.

The total cost is O(n log n) for the sort and O(n) for the scan. For queries that must be answered online, move to prefix sums or Fenwick and Segment Trees; for the "scheduling by sorting" family, see Greedy Algorithms and How to Trust Them.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does it mean that Python's sorted is stable?

    Stability lets you sort by the less important criterion first and the more important one last, and equal elements keep the earlier order.
  2. 2. Why are tuples of (time, delta) with delta -1 for ends and +1 for starts sorted correctly for half-open intervals?

    At equal times the smaller delta comes first. An interval ending at t frees its slot before an interval starting at t takes one, as half-open [s, e) requires.
  3. 3. What does coordinate compression preserve?

    Ranks keep the order of distinct values. Distances are lost, so keep the sorted list of original coordinates when you need them.
  4. 4. When is functools.cmp_to_key the right tool?

    cmp_to_key adapts a pairwise comparison into a key. It is slower than a plain key, so use it only when a key function cannot express the order.

Summary

  • A sort key can be a tuple; negate numbers for descending order, or use stable multi-pass sorting.
  • functools.cmp_to_key handles orders defined by pairwise comparison, such as concatenating numbers into the largest result.
  • Sort indexes when you must remember original positions.
  • Coordinate compression maps large values to ranks so arrays and difference arrays become possible.
  • A sweep line turns intervals into start and end events, sorts them, and scans with a running state.
  • Decide the tie rule first: ends before starts for half-open intervals, the reverse for closed ones.

Next: Modular Arithmetic