Intervals

Your calendar has five meetings today, entered in no particular order: 13–15, 9–11, 10–12, 16–17 and 14–16. A colleague asks when you are busy. They do not want five meetings. They want the busy stretches: 9 to 12, and 13 to 17.

Each meeting is an interval, a start and an end. Intervals show up everywhere: bookings, shifts, video segments, ranges of IP addresses, the lines a code review comment covers. Most interval problems are solved the same way: sort them, then walk through once.

#When do two intervals overlap

Start with two intervals, a and b. There are many ways to overlap (partly, fully inside, identical) and only two ways not to: a ends before b starts, or b ends before a starts. So test the two easy cases and flip the result.

// Touching counts as overlapping here. Use < instead of <= if it should not.
function overlaps(a, b) {
  return a[0] <= b[1] && b[0] <= a[1];
}

# Touching counts as overlapping here. Use < instead of <= if it should not.
def overlaps(a, b):
    return a[0] <= b[1] and b[0] <= a[1]

Whether touching intervals overlap is a rule of the problem, not of the code. In a calendar, 14–16 and 16–17 make one busy stretch. For room bookings, a meeting ending at 16 does not block one starting at 16. Decide once, then use the same < or <= everywhere.

#The idea: sort by start, then sweep

Comparing every pair of meetings is O(n²). Sorting by start time fixes that. Once sorted, a meeting can only overlap the block you are building right now, never an earlier block, because everything earlier has already ended.

So keep one open block. For each next meeting, ask one question: does it start before the open block ends? If yes, stretch the block's end. If no, close the block and open a new one.

sort meetings by startbusy = [first meeting]for each next meeting (start, end):  last = the final block in busy  if start <= last.end: last.end = max(last.end, end)  else: add (start, end) as a new block

function mergeBusy(meetings) {
  if (meetings.length === 0) return [];
  const sorted = [...meetings].sort((a, b) => a[0] - b[0]);
  const busy = [[...sorted[0]]];
  for (const [start, end] of sorted.slice(1)) {
    const last = busy[busy.length - 1];
    if (start <= last[1]) {
      last[1] = Math.max(last[1], end); // overlaps or touches: stretch
    } else {
      busy.push([start, end]);          // gap: new block
    }
  }
  return busy;
}
 
mergeBusy([[13, 15], [9, 11], [10, 12], [16, 17], [14, 16]]);
// [[9, 12], [13, 17]]

def merge_busy(meetings):
    if not meetings:
        return []
    ordered = sorted(meetings, key=lambda m: m[0])
    busy = [list(ordered[0])]
    for start, end in ordered[1:]:
        last = busy[-1]
        if start <= last[1]:
            last[1] = max(last[1], end)  # overlaps or touches: stretch
        else:
            busy.append([start, end])    # gap: new block
    return busy
 
merge_busy([[13, 15], [9, 11], [10, 12], [16, 17], [14, 16]])
# [[9, 12], [13, 17]]

The code copies the first meeting instead of using it directly. Otherwise stretching the block would quietly change the caller's data.

#How many at the same time

A different question: the office has to host meetings 9–12, 10–11, 11–13 and 13–14. How many rooms does it need? That is the largest number of meetings running at any one moment.

Stop thinking of meetings and think of events. Each meeting is a +1 when it starts and a −1 when it ends. Sort all the events by time and walk through them with a counter. The highest the counter ever reaches is the answer. When an end and a start happen at the same time, process the end first: the person leaving at 11 frees the room for the one arriving at 11.

events = (start, +1) and (end, −1) for each meetingsort events by time; at a tie, −1 before +1for each event:  inUse += change; most = max(most, inUse)

function roomsNeeded(meetings) {
  const events = [];
  for (const [start, end] of meetings) {
    events.push([start, 1], [end, -1]);
  }
  // by time; at a tie, -1 (an end) sorts before +1 (a start)
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  let inUse = 0;
  let most = 0;
  for (const [, change] of events) {
    inUse += change;
    most = Math.max(most, inUse);
  }
  return most;
}
 
roomsNeeded([[9, 12], [10, 11], [11, 13], [13, 14]]); // 2

def rooms_needed(meetings):
    events = []
    for start, end in meetings:
        events.append((start, 1))
        events.append((end, -1))
    # tuples sort by time, then by change, so -1 (an end) comes before +1
    events.sort()
    in_use = most = 0
    for _, change in events:
        in_use += change
        most = max(most, in_use)
    return most
 
rooms_needed([[9, 12], [10, 11], [11, 13], [13, 14]])  # 2

Counting rooms costs O(n log n) time for the sort and O(n) space for the 2n events. A third classic question, "keep as many meetings as possible with no overlaps", is solved by sorting on end time instead; it is worked through in Greedy Algorithms.

#Common mistakes

#Check yourself

#What to practise next

Interval problems mix with the other techniques in this module: sort-and-sweep is the same habit you saw in Greedy Algorithms. Next, Bit Manipulation changes gear completely and works on the individual bits of a number.