Sorted interval sweep

When to use it

Use it when the input is a list of start and end pairs and the question is how they overlap, touch or leave gaps, with nothing to choose.

It belongs to the optimization group: Find the best answer without trying every possibility: reuse smaller answers, or take the safe choice first.

Watch it work

A beach has at least one lifeguard shift. Each shift is a pair [start, end], in hours after the beach opens, and the shifts come in no order. Return every gap between shifts: each stretch of time, as [start, end], with no lifeguard on duty.

Input
shifts = [[3, 5], [0, 4], [7, 8], [1, 2]]

Output
[[5, 7]]

The method

1. Sort the shifts by start, earliest first
2. Keep the latest end among the shifts seen so far
3. A shift that starts after that end leaves a gap before it
4. Move the latest end forward if this shift ends later
5. Return the gaps

The run, one moment at a time

1. Step 1. The 4 shifts in the order given. Each row is one shift, and "on" marks its hours. In this order, finding a gap would mean comparing every shift with all the others.

   hour: 0-1 1-2 2-3 3-4 4-5 5-6 6-7 7-8
   3 to 5: · · · on on · · ·
   0 to 4: on on on on · · · ·
   7 to 8: · · · · · · · on
   1 to 2: · on · · · · · ·
   gaps: empty
   

2. Step 1. Sorted by start, earliest first. Every shift that began earlier is now above the one you look at, so one number can stand for all of them: their latest end.

   hour: 0-1 1-2 2-3 3-4 4-5 5-6 6-7 7-8
   0 to 4: on on on on · · · ·
   1 to 2: · on · · · · · ·
   3 to 5: · · · on on · · ·
   7 to 8: · · · · · · · on
   gaps: empty
   

3. Step 2. The first shift ends at 4, so the latest end so far is 4. Someone is on duty from hour 0 up to hour 4.

   hour: 0-1 1-2 2-3 3-4 4-5 5-6 6-7 7-8
   0 to 4: on on on on · · · ·
   1 to 2: · on · · · · · ·
   3 to 5: · · · on on · · ·
   7 to 8: · · · · · · · on
   gaps: empty
   

4. Step 3. The shift 1 to 2 starts at 1. That is not after the latest end, 4. Someone is still on duty, so there is no gap.

   hour: 0-1 1-2 2-3 3-4 4-5 5-6 6-7 7-8
   0 to 4: on on on on · · · ·
   1 to 2: · on · · · · · ·
   3 to 5: · · · on on · · ·
   7 to 8: · · · · · · · on
   gaps: empty
   

5. Step 4. It ends at 2, which is not later than 4, so the latest end stays 4. The shift that ends at 4 is still on duty after this one has ended.

   hour: 0-1 1-2 2-3 3-4 4-5 5-6 6-7 7-8
   0 to 4: on on on on · · · ·
   1 to 2: · on · · · · · ·
   3 to 5: · · · on on · · ·
   7 to 8: · · · · · · · on
   gaps: empty
   

6. Step 3. The shift 3 to 5 starts at 3. The shift above it ended at 2, but the latest end is 4, and 3 is not after 4. Someone is still on duty, so there is no gap.

   hour: 0-1 1-2 2-3 3-4 4-5 5-6 6-7 7-8
   0 to 4: on on on on · · · ·
   1 to 2: · on · · · · · ·
   3 to 5: · · · on on · · ·
   7 to 8: · · · · · · · on
   gaps: empty
   

7. Step 4. It ends at 5, later than 4, so the latest end moves forward to 5.

   hour: 0-1 1-2 2-3 3-4 4-5 5-6 6-7 7-8
   0 to 4: on on on on · · · ·
   1 to 2: · on · · · · · ·
   3 to 5: · · · on on · · ·
   7 to 8: · · · · · · · on
   gaps: empty
   

8. Step 3. The shift 7 to 8 starts at 7, after the latest end, 5. Nobody is on duty from 5 to 7, so [5, 7] is a gap.

   hour: 0-1 1-2 2-3 3-4 4-5 5-6 6-7 7-8
   0 to 4: on on on on · · · ·
   1 to 2: · on · · · · · ·
   3 to 5: · · · on on · · ·
   7 to 8: · · · · · · · on
   gaps: 5-7
   

9. Step 4. It ends at 8, later than 5, so the latest end moves forward to 8.

   hour: 0-1 1-2 2-3 3-4 4-5 5-6 6-7 7-8
   0 to 4: on on on on · · · ·
   1 to 2: · on · · · · · ·
   3 to 5: · · · on on · · ·
   7 to 8: · · · · · · · on
   gaps: 5-7
   

10. Step 5. One sort, then one walk over the 4 shifts. There is one gap, from hour 5 to hour 7, with no lifeguard on duty.

    hour: 0-1 1-2 2-3 3-4 4-5 5-6 6-7 7-8
    0 to 4: on on on on · · · ·
    1 to 2: · on · · · · · ·
    3 to 5: · · · on on · · ·
    7 to 8: · · · · · · · on
    gaps: 5-7
    

The code

The numbered comments are the steps of the method.

function solve(shifts) {
  // 1. Sort the shifts by start, earliest first
  const ordered = [...shifts].sort((a, b) => a[0] - b[0]);
  // 2. Keep the latest end among the shifts seen so far
  let latest = ordered[0][1];
  const gaps = [];
  for (let i = 1; i < ordered.length; i++) {
    const [start, end] = ordered[i];
    // 3. A shift that starts after that end leaves a gap before it
    if (start > latest) gaps.push([latest, start]);
    // 4. Move the latest end forward if this shift ends later
    latest = Math.max(latest, end);
  }
  // 5. Return the gaps
  return gaps;
}

def solve(shifts):
    # 1. Sort the shifts by start, earliest first
    ordered = sorted(shifts, key=lambda shift: shift[0])
    # 2. Keep the latest end among the shifts seen so far
    latest = ordered[0][1]
    gaps = []
    for start, end in ordered[1:]:
        # 3. A shift that starts after that end leaves a gap before it
        if start > latest:
            gaps.append([latest, start])
        # 4. Move the latest end forward if this shift ends later
        latest = max(latest, end)
    # 5. Return the gaps
    return gaps

How to spot it

Given: A list of intervals, each a start and an end, in no order

Sorted by start, the intervals that can touch each other become neighbors, so one walk compares each with what came before it.

Asked: Do any two of the bookings overlap?

After sorting by start, an overlap always shows between neighbors: a booking starts before the latest end so far. No other pair needs a look.

Asked: The largest number of visits going on at the same moment

Sort every start and every end as moments in time. Walking them in order, a count goes up at a start and down at an end.

Limits: Up to 100,000 intervals, so comparing every pair is too slow

Every pair is about 5 billion comparisons. Sorting takes about 1.7 million steps, and the walk after it 100,000.

Looks like it, but is not

• Keep as many intervals as you can so that no two of them overlap. Use Greedy choice. There you choose which intervals stay. Sort by end and always keep the one that ends first, because it leaves the most room.
• The intervals are already sorted and do not overlap, and you must find the one that holds a given time. Use Binary search on a sorted range. Nothing has to be walked. In a sorted list, halving finds the right interval in a few steps.
• Find the longest run of neighbors in one list that meets a condition. Use Variable sliding window. That run is a stretch you grow and shrink yourself inside one list. Here the stretches are given, as pairs of start and end.

Cost and mistakes

Sorting takes about n log n steps, written O(n log n), and that is the larger part: the walk after it is n steps. Extra space is the sorted copy, n intervals, and the answer.

Watch out

• Compare with the latest end, not with the end of the interval before. A long interval can still be running when a short one inside it ends. In the example that mistake reports a gap from 2 to 3.
• Decide what touching means before you write the test. If an interval that starts exactly when another ends counts as overlapping, compare with <=; if it does not, with <.

In the 150

4 problems of the 150 use it. Naming them gives their method away, so the list is folded.