The Line Sweep Technique for Intervals

The Line Sweep Technique for Intervals

What is an interval?

Many array problems give you data that is not just single numbers, but *ranges*. We call such a range an interval.

An interval is just two values: a start and an end. Think of a number line — the kind you drew in school, with numbers going left to right. An interval is a piece of that line, like "from 2 to 5". It has a left edge (start = 2) and a right edge (end = 5).

The number line can stand for anything that grows in one direction:

• Time — a meeting from 2 PM to 5 PM.
• Distance — a road from kilometre 2 to kilometre 5.

In code we usually store each interval as a pair, and we keep many of them together in an array. For example, each box in the array holds one (start, end) pair.

The problem these techniques solve

When you have a bunch of intervals, you often want to answer questions like:

• Do any of them overlap?
• Can I merge the ones that touch?
• How many intervals are "active" at the same moment?

You *could* compare every interval with every other interval, but that is slow. The line sweep technique (also called the *sweep line algorithm*) is a smarter, faster way.

The big idea

Imagine a vertical line standing on the number line. Now slowly drag that line from the far left to the far right. As it moves, it crosses the start edges and end edges of your intervals one by one, in order.

Every time the line touches an edge, something *happens* — an interval begins, or an interval ends. We call these moments events. The line sweep technique handles these events one at a time, in left-to-right order, while keeping a small piece of bookkeeping (a counter, a set, or a list) that remembers what is going on right now.

That is the whole trick: instead of looking at all intervals at once, you walk past their edges in order and react to each one.

Step 1 — Sort the events

The sweep only works if the events are in order from left to right. So the first step is always to sort the intervals.

We sort them in non-decreasing order (smallest first, ties allowed) — usually by their start value. If two intervals have the same start, we break the tie using their end value.

Here is the example from the lesson. The original array is unsorted:

index:   0       1       2       3
        2,5     6,9     5,7     1,4

After sorting by start (and then by end):

index:   0       1       2       3
        1,4     2,5     5,7     6,9

Now the array reads left to right just like the x-axis of a number line. Walking through the array from index 0 to the end is the *same* as moving rightward along the line. That is exactly what lets us "sweep".

Step 2 — Sweep the line

Once the array is sorted, we simply traverse it once, from the first index to the last. Each step forward is one move of our imaginary vertical line to the right.

As we visit each interval, we update our bookkeeping:

• We might add the interval to an "active" set when it starts.
• We might remove it when it ends.
• We might count how many are active, or join ones that overlap.

Exactly what we do depends on the problem — but the shape is always the same: *sorted scan, update state, move on*. By the time the line passes the last edge, the sweep is complete and we have our answer.

You can picture it as the line stopping at each interval in 1,4, 2,5, 5,7, 6,9 in turn, processing it, then sliding on to the next.

Why it is fast — complexity

Let N be the number of intervals.

1. Sorting the array takes O(N log N) time.
2. Sweeping (one pass through the sorted array) takes O(N) time.

The sorting step is the slower of the two, so the total time is:

> Time complexity: O(N log N) — in the best, average, and worst case.

For space, it depends on whether we can sort the original array directly:

• Best case: we sort the array *in place*, using no extra storage → O(1) space.
• Worst case: we must keep the input unchanged and sort a *copy* → O(N) space.

This is much better than comparing every pair of intervals (which would be O(N²)), and that speed-up is exactly why line sweep is such a popular tool for interval problems.