Interval conventions and overlap tests

An interval is the stretch between two endpoints, a start and an end, and two decisions settle most interval problems: whether the end belongs to the interval, and how two intervals are compared. A closed interval [a, b] contains both endpoints. A half-open interval [a, b) contains its start but not its end, so a booking from 09:00 to 10:00 and one from 10:00 to 11:00 share no minute, and one room can host both. Two non-empty half-open intervals overlap exactly when each starts before the other ends: a1 < b2 and a2 < b1. For closed intervals, both comparisons become <=. Sort intervals by start to merge them or to look for a clash, and by end to keep as many as possible with no two overlapping. Before any of that, turn the input into numbers you can trust: times as minutes, endpoints in order, and a decision about empty intervals. This lesson checks four overlap tests on every pair of small intervals, normalises clock times, compares three sort orders, and solves one problem in full in five languages.

Closed or half-open: what the end means

Take two bookings for one room: A from 09:00 to 10:00 and B from 10:00 to 11:00. Whether they clash depends only on whether 10:00 belongs to A:

The three conventions side by side, with how many whole numbers each holds when its ends are whole numbers:

• Closed [a, b] contains both ends, b − a + 1 whole numbers. It suits days, seats and pages “from 3 to 7, both included”.
• Half-open [a, b) contains its start but not its end, b − a whole numbers. It suits meeting and booking times, and the index ranges of most libraries.
• Open (a, b) contains neither end, b − a − 1 whole numbers. It is rare in coding rounds: a problem says “strictly between” when it means one.

So closed [a, b] and [b, c] overlap at b, while half-open [a, b) and [b, c) share nothing, and neither do open intervals that meet.

Half-open intervals are the default for times and indices because three things come out simple. The length is b - a, with no + 1. Two intervals that meet, such as [09:00, 10:00) and [10:00, 11:00), share the bound with no overlap and no gap, so a morning can be cut into slots that cover it exactly. And an empty interval is just [a, a). Dijkstra’s note “Why numbering should start at zero” (EWD 831) makes the same case for writing a range of whole numbers as a ≤ i < b. Most libraries agree, and so does the calendar standard:

• Python’s slice s[i:j] holds the items with index k where i <= k < j, and range(start, stop) stops before stop.
• Java’s List.subList(fromIndex, toIndex) includes fromIndex and excludes toIndex.
• Go’s slice a[low:high] has length high - low.
• JavaScript’s slice(start, end) returns the elements from start up to, but not including, end.
• C++ algorithms take ranges [first, last) that stop just before last.
• iCalendar (RFC 5545), the format calendars exchange events in, defines an event’s DTEND as its non-inclusive end.

Closed intervals turn up when a problem counts whole units: “days 3 to 7”, “rows 10 to 20 inclusive”, “seats 1 to 4”. Convert them on the way in. A closed range of whole numbers [a, b] is the half-open [a, b + 1), so days 3 to 7 become [3, 8), which holds 8 − 3 = 5 days. After that one conversion, a single overlap test, a single length formula and a single meaning of “touching” serve the whole solution, and you convert back only if the output must be closed.

One question survives the conversion. As whole numbers, [3, 5] and [6, 8] leave no day out between them, and as half-open intervals, [3, 6) and [6, 9), they touch. Whether such neighbours should be merged, or count as a clash, depends on the problem, so ask.

The overlap test in two comparisons

Two half-open intervals [a1, b1) and [a2, b2), each with its start before its end, are disjoint exactly when one of them has ended by the time the other starts: b1 <= a2 or b2 <= a1. Negate both sides, and the two conditions joined by or become two conditions joined by and, with each comparison turned round: the intervals overlap exactly when a1 < b2 and a2 < b1. In words, each starts before the other ends. For closed intervals, ending at the very point where the other starts already means sharing that point, so they are disjoint when b1 < a2 or b2 < a1, and they overlap when a1 <= b2 and a2 <= b1.

The same test has a second form that also names the shared part. Two intervals share the stretch from the later start to the earlier end, [max(a1, a2), min(b1, b2)), so they overlap exactly when that stretch is not empty: max(a1, a2) < min(b1, b2). The length of the overlap is max(0, min(b1, b2) - max(a1, a2)).

Plausible-looking versions of this test are easy to write and hard to check by eye. So here are four of them, tried on every ordered pair of intervals whose endpoints are whole numbers from 0 to 6, against the truth worked out by brute force, the set of whole numbers both intervals contain:

"""Four ways to test whether two intervals overlap, checked on every pair of small intervals."""

LIMIT = 6  # every endpoint is a whole number from 0 to 6


def shares_a_point(first, second, closed):
    """The truth, by brute force: do the two intervals have a whole number in common?"""

    def points(interval):
        start, end = interval
        return set(range(start, end + 1 if closed else end))

    return bool(points(first) & points(second))


HALF_OPEN_TESTS = {
    "a1 < b2 and a2 < b1": lambda a1, b1, a2, b2: a1 < b2 and a2 < b1,
    "max(a1, a2) < min(b1, b2)": lambda a1, b1, a2, b2: max(a1, a2) < min(b1, b2),
    "a1 <= b2 and a2 <= b1": lambda a1, b1, a2, b2: a1 <= b2 and a2 <= b1,
    "a2 or b2 inside the first": lambda a1, b1, a2, b2: a1 <= a2 < b1 or a1 < b2 <= b1,
}
CLOSED_TESTS = {
    "a1 <= b2 and a2 <= b1": lambda a1, b1, a2, b2: a1 <= b2 and a2 <= b1,
    "a1 < b2 and a2 < b1": lambda a1, b1, a2, b2: a1 < b2 and a2 < b1,
}


def wrong_answers(test, intervals, closed):
    """How many ordered pairs the test gets wrong, and the first of them."""
    wrong, example = 0, None
    for first in intervals:
        for second in intervals:
            if test(*first, *second) != shares_a_point(first, second, closed):
                wrong += 1
                example = example or (first, second)
    return wrong, example


def report(title, tests, intervals, closed):
    print(f"{title}: {len(intervals)} intervals, {len(intervals) ** 2} ordered pairs")
    for name, test in tests.items():
        wrong, example = wrong_answers(test, intervals, closed)
        first = "" if example is None else f", first {example[0]} and {example[1]}"
        print(f"  {name:<27} wrong on {wrong:>3}{first}")


every = [(a, b) for a in range(LIMIT + 1) for b in range(a, LIMIT + 1)]
non_empty = [(a, b) for a, b in every if a < b]

report("Half-open [a, b) with a < b", HALF_OPEN_TESTS, non_empty, closed=False)
report("Half-open, empty ones too", HALF_OPEN_TESTS, every, closed=False)
report("Closed [a, b] with a <= b", CLOSED_TESTS, every, closed=True)

Half-open [a, b) with a < b: 21 intervals, 441 ordered pairs
  a1 < b2 and a2 < b1         wrong on   0
  max(a1, a2) < min(b1, b2)   wrong on   0
  a1 <= b2 and a2 <= b1       wrong on  70, first (0, 1) and (1, 2)
  a2 or b2 inside the first   wrong on  35, first (1, 2) and (0, 3)
Half-open, empty ones too: 28 intervals, 784 ordered pairs
  a1 < b2 and a2 < b1         wrong on  70, first (0, 2) and (1, 1)
  max(a1, a2) < min(b1, b2)   wrong on   0
  a1 <= b2 and a2 <= b1       wrong on 231, first (0, 0) and (0, 0)
  a2 or b2 inside the first   wrong on 112, first (0, 1) and (0, 0)
Closed [a, b] with a <= b: 28 intervals, 784 ordered pairs
  a1 <= b2 and a2 <= b1       wrong on   0
  a1 < b2 and a2 < b1         wrong on 161, first (0, 0) and (0, 0)

What the counts say:

• On non-empty half-open intervals, the two correct forms agree with the truth on all 441 pairs.
• The closed test, a1 <= b2 and a2 <= b1, is wrong on 70 pairs, and they are exactly the pairs that touch, such as [0, 1) and [1, 2): on half-open data it turns every back-to-back booking into a clash.
• The endpoint test, “the second interval’s start or end lies inside the first”, is wrong on 35 pairs. Each is a pair where the second interval contains the first with room on both sides, such as [0, 3) around [1, 2): neither end of the long interval lies inside the short one, yet they overlap. There are 35 such pairs because each is a choice of four different endpoints from the seven values 0 to 6.
• Allow empty intervals, [a, a), and the cross test a1 < b2 and a2 < b1 goes wrong on 70 pairs: it says that the empty interval at 1 overlaps [0, 2), though the empty interval contains nothing. The max-min form stays right, because max(a1, a2) < min(b1, b2) can only hold when both intervals are non-empty. So either drop empty intervals before you test, or use the max-min form.
• On closed intervals, the half-open test is wrong on 161 pairs: every pair in which one interval starts at the very point where the other ends, such as [0, 1] and [1, 2], or a one-point interval [2, 2] at an end of another.

An exhaustive check of small cases is not a proof (the proof is the two lines at the start of this section), but it finds the cases a proof forgot to consider, and the 2,009 pairs above take a fraction of a second.

Normalise the input before you compare

The tests above assume clean numbers. Real inputs arrive as text, with ends in either order, sometimes empty and sometimes from another time zone. Settle all of it at the start, in one place, and the rest of the solution stays simple. Here is a day’s worth of start times, and what Python makes of them:

"""Turning clock times into numbers before comparing them."""

from datetime import time, timedelta, timezone


def minutes(text):
    """'H:MM' or 'HH:MM' on a 24-hour clock, as minutes after midnight. '24:00' is the end of the day, 1440."""
    hours, mins = (int(part) for part in text.split(":"))
    if not (0 <= hours <= 24 and 0 <= mins < 60) or (hours == 24 and mins > 0):
        raise ValueError(f"not a time of day: {text!r}")
    return hours * 60 + mins


def attempt(parse, text):
    """What a parser makes of text, or the name of the error it raises."""
    try:
        return str(parse(text))
    except ValueError:
        return "ValueError"


starts = ["10:00", "9:30", "09:45", "13:15", "8:05"]
print("sorted as text:   ", sorted(starts))
print("sorted by minutes:", sorted(starts, key=minutes))
print()

for text in ["09:30", "9:30", "24:00"]:
    iso = attempt(time.fromisoformat, text)
    strp = attempt(lambda t: time.strptime(t, "%H:%M"), text)
    print(f"{text:>5}: fromisoformat {iso:<10}  strptime {strp:<10}  minutes {minutes(text)}")
print()

# A night shift from 22:00 to 02:00 crosses midnight. On one timeline its end falls on the next day.
start, end = minutes("22:00"), minutes("02:00")
if end < start:
    end += 24 * 60
print(f"night shift 22:00 to 02:00: [{start}, {end}), {end - start} minutes")

# Times from two time zones: convert both to one zone first.
# A time without a zone cannot be ordered against a time with one.
ist = timezone(timedelta(hours=5, minutes=30))
print("09:00 at UTC+05:30 equals 03:30 UTC:", time(9, 0, tzinfo=ist) == time(3, 30, tzinfo=timezone.utc))
try:
    time(9, 0) < time(3, 30, tzinfo=timezone.utc)
except TypeError as error:
    print("TypeError:", error)

sorted as text:    ['09:45', '10:00', '13:15', '8:05', '9:30']
sorted by minutes: ['8:05', '9:30', '09:45', '10:00', '13:15']

09:30: fromisoformat 09:30:00    strptime 09:30:00    minutes 570
 9:30: fromisoformat ValueError  strptime 09:30:00    minutes 570
24:00: fromisoformat 00:00:00    strptime ValueError  minutes 1440

night shift 22:00 to 02:00: [1320, 1560), 240 minutes
09:00 at UTC+05:30 equals 03:30 UTC: True
TypeError: can't compare offset-naive and offset-aware times

Times as text. Sorted as text, “8:05” and “9:30” come after “13:15”, because Python compares strings character by character, by their Unicode code points, and the character 9 comes after 1. Text order matches clock order only when every time has the same zero-padded width, as “09:30” and “13:15” do. Minutes after midnight, the hours times 60 plus the minutes, compare correctly whatever the padding.

The library’s parsers disagree at the edges. time.fromisoformat reads ISO 8601 times, and it rejects “9:30”, with its single digit for the hour. time.strptime with "%H:%M", a class method added in Python 3.14, accepts “9:30”, because its documentation makes the leading zero optional when it parses, but it rejects “24:00”, since hours run from 0 to 23. And on the Python this track runs, time.fromisoformat("24:00") returns 00:00:00, the start of the day, so a booking from 23:00 to 24:00 would end before it starts. A function of three lines that splits on the colon does exactly what the problem says, and it can let “24:00” mean 1,440, the end of the day.

An end before its start means different things in different problems. For the two ends of a segment on a line, swap them: (7, 3) is the interval [3, 7). For clock times, 22:00 to 02:00 is a night shift that crosses midnight. On one timeline, add 1,440 minutes to its end, which gives [1320, 1560), 240 minutes, as the example printed; inside a single day, split it into [22:00, 24:00) and [00:00, 02:00). An end equal to its start, such as 10:00 to 10:00, is either an empty interval or a whole day. Each of these is a question for the interviewer, never a guess.

Empty intervals need a decision too. A half-open [10:00, 10:00) contains no minute, so it can clash with nothing, yet the cross test says it overlaps any booking that runs across 10:00, as the counts above showed. Drop empty intervals at the start, or use the max-min test.

Sort by start or by end, for the right reason

Most interval solutions sort first, and the key to sort by depends on the question.

Sort by start to merge intervals or to look for a clash. In start order, everything that can still overlap the next interval has started already, so one pass with a little memory decides: the end of the previous interval, to ask whether any two clash (the problem below proves that this is enough), or the latest end so far, to merge overlapping intervals into one, which the next lesson builds.

Sort by end to keep as many intervals as possible with no two overlapping. The interval that ends first leaves the most time for the others, so a scan in order of end keeps each interval that starts no earlier than the end of the last one kept. The two other orders that come to mind both fail on small inputs. This example keeps bookings greedily in three orders and compares the counts with the best possible, found by trying every subset:

"""Keep as many bookings as possible with no two overlapping: which order should a greedy scan use?"""

from itertools import combinations


def overlaps(first, second):
    """Half-open intervals [start, end) with start < end."""
    return first[0] < second[1] and second[0] < first[1]


def greedy(bookings, key):
    """Takes the bookings in the order of key and keeps each one that overlaps none of those already kept."""
    kept = []
    for booking in sorted(bookings, key=key):
        if not any(overlaps(booking, other) for other in kept):
            kept.append(booking)
    return len(kept)


def best_possible(bookings):
    """The most bookings that fit together, by trying every subset (fine for a handful)."""
    for size in range(len(bookings), 0, -1):
        for group in combinations(bookings, size):
            if not any(overlaps(a, b) for a, b in combinations(group, 2)):
                return size
    return 0


ORDERS = {
    "by start": lambda b: b[0],
    "shortest": lambda b: b[1] - b[0],  # shortest first
    "by end": lambda b: b[1],
}
DAYS = {
    "day one": [(0, 10), (1, 3), (3, 5), (5, 7)],
    "day two": [(0, 4), (3, 5), (4, 8)],
}

# For each day: the most bookings that fit together, then how many each greedy order keeps.
for day, bookings in DAYS.items():
    print(f"{day}: best {best_possible(bookings)}")
    for name, key in ORDERS.items():
        print(f"  {name:<10}{greedy(bookings, key)}")

day one: best 3
  by start  1
  shortest  3
  by end    3
day two: best 2
  by start  2
  shortest  1
  by end    2

Day one is [0, 10), [1, 3), [3, 5) and [5, 7). In order of start, the scan keeps [0, 10) first, and that one long booking blocks the other three: 1 kept, where 3 fit. Shortest first looks like the fix and works on day one, but day two, [0, 4), [3, 5) and [4, 8), defeats it: the shortest booking, [3, 5), overlaps both others, so the scan keeps 1 where 2 fit. The order of end is right on both days, and the lesson on the fewest removals proves that it is always right.

A problem solved in full: one job at a time

This section takes one problem from start to finish, step by step as an interviewer expects to hear it: a slow answer that is plainly right, the observation that leads to a faster one, the faster plan with its proof, a trace by hand, its cost, five implementations, a random test against the slow answer, the edge cases, and three questions an interviewer might ask next.

Three logs serve as examples. [(3600, 5400), (0, 3600), (5400, 9000)] answers True: its jobs touch at 3,600 and 5,400 but never overlap. [(0, 3600), (7200, 9000), (3000, 4000)] answers False, because the first and the last job both hold the server from 3,000 to 3,600. [(0, 86400), (40000, 40060)] answers False too: a one-minute job sits inside a day-long one.

Brute force first

Compare every pair of jobs with the overlap test:

from itertools import combinations


def one_at_a_time_brute(jobs):
    """Compares every pair of jobs with the overlap test: n(n - 1)/2 pairs."""
    for (start1, end1), (start2, end2) in combinations(jobs, 2):
        if start1 < end2 and start2 < end1:
            return False
    return True


if __name__ == "__main__":
    print(one_at_a_time_brute([(3600, 5400), (0, 3600), (5400, 9000)]))
    print(one_at_a_time_brute([(0, 3600), (7200, 9000), (3000, 4000)]))
    print(one_at_a_time_brute([(0, 86400), (40000, 40060)]))

True
False
False

It is right by construction, so keep it: it checks the fast version below. It is also slow. A log of 200,000 jobs has 200,000 × 199,999 ÷ 2, about 2 × 10¹⁰ pairs. At the planning rate of the lesson on reading constraints, roughly 10⁷ simple steps a second for CPython, that is more than half an hour; compiled code, at roughly 10⁸ a second, would still need more than three minutes.

What to notice

The brute force compares jobs that are hours apart, which can never clash, as carefully as jobs that are side by side. Put the jobs in time order and look at them the way the server saw them: a clash means that a job started while the one before it was still running. That suggests sorting by start and comparing each job only with its neighbour. The question is whether a clash between two jobs that are far apart in the sorted list can hide from that check, and the proof below shows that it cannot.

The fast version, step by step

1. Sort a copy of the log by start.
2. Walk through the sorted jobs. If a job starts before the job just before it has ended, return False.
3. If no job does, return True.

The Python and JavaScript tabs run in your browser; the Java, C++ and Go tabs show the same plan in those languages:

from itertools import pairwise


def one_at_a_time(jobs):
    """True when no two jobs overlap. Each job is (start, end), the half-open interval [start, end), start < end."""
    in_order = sorted(jobs)  # by start, and by end when two jobs start together
    for before, after in pairwise(in_order):
        if after[0] < before[1]:  # the next job starts before the one before it has ended
            return False
    return True


if __name__ == "__main__":
    print(one_at_a_time([(3600, 5400), (0, 3600), (5400, 9000)]))
    print(one_at_a_time([(0, 3600), (7200, 9000), (3000, 4000)]))
    print(one_at_a_time([(0, 86400), (40000, 40060)]))

    # The largest log: 200,000 jobs of 100 seconds each, back to back, listed latest first.
    log = [(100 * i, 100 * i + 100) for i in reversed(range(200_000))]
    print(one_at_a_time(log))
    log[0] = (log[0][0] - 1, log[0][1])  # the latest job now starts 1 second early
    print(one_at_a_time(log))

True
False
False
True
False

// True when no two jobs overlap. Each job is [start, end], the half-open interval [start, end), start < end.
function oneAtATime(jobs) {
  // Compare numbers: without a compare function, sort() would order the jobs as text.
  const inOrder = [...jobs].sort((x, y) => x[0] - y[0] || x[1] - y[1]);
  for (let i = 1; i < inOrder.length; i++) {
    if (inOrder[i][0] < inOrder[i - 1][1]) return false; // starts before the job before it has ended
  }
  return true;
}

console.log(oneAtATime([[3600, 5400], [0, 3600], [5400, 9000]]));
console.log(oneAtATime([[0, 3600], [7200, 9000], [3000, 4000]]));
console.log(oneAtATime([[0, 86400], [40000, 40060]]));

// The largest log: 200,000 jobs of 100 seconds each, back to back, listed latest first.
const log = Array.from({ length: 200_000 }, (_, k) => {
  const i = 199_999 - k;
  return [100 * i, 100 * i + 100];
});
console.log(oneAtATime(log));
log[0] = [log[0][0] - 1, log[0][1]]; // the latest job now starts 1 second early
console.log(oneAtATime(log));

true
false
false
true
false

import java.util.Arrays;
import java.util.Comparator;

public class OneAtATime {
    /** True when no two jobs overlap. Each job is {start, end}, the half-open interval [start, end), start < end. */
    static boolean oneAtATime(int[][] jobs) {
        int[][] inOrder = jobs.clone(); // a copy of the array, so the caller's log keeps its order
        Arrays.sort(inOrder, Comparator.comparingInt((int[] job) -> job[0]).thenComparingInt(job -> job[1]));
        for (int i = 1; i < inOrder.length; i++) {
            if (inOrder[i][0] < inOrder[i - 1][1]) return false; // starts before the job before it has ended
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(oneAtATime(new int[][] {{3600, 5400}, {0, 3600}, {5400, 9000}}));
        System.out.println(oneAtATime(new int[][] {{0, 3600}, {7200, 9000}, {3000, 4000}}));
        System.out.println(oneAtATime(new int[][] {{0, 86400}, {40000, 40060}}));

        // The largest log: 200,000 jobs of 100 seconds each, back to back, listed latest first.
        int[][] log = new int[200_000][];
        for (int k = 0; k < log.length; k++) {
            int i = log.length - 1 - k;
            log[k] = new int[] {100 * i, 100 * i + 100};
        }
        System.out.println(oneAtATime(log));
        log[0] = new int[] {log[0][0] - 1, log[0][1]}; // the latest job now starts 1 second early
        System.out.println(oneAtATime(log));
    }
}

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

using Job = std::pair<int, int>;  // {start, end}: the half-open interval [start, end), start < end

// True when no two jobs overlap. The log is taken by value, so sorting it leaves the caller's copy alone.
bool one_at_a_time(std::vector<Job> jobs) {
    std::ranges::sort(jobs);  // pairs compare by start, then by end
    for (std::size_t i = 1; i < jobs.size(); ++i) {
        if (jobs[i].first < jobs[i - 1].second) return false;  // starts before the job before it has ended
    }
    return true;
}

int main() {
    std::cout << std::boolalpha;
    std::cout << one_at_a_time({{3600, 5400}, {0, 3600}, {5400, 9000}}) << '\n';
    std::cout << one_at_a_time({{0, 3600}, {7200, 9000}, {3000, 4000}}) << '\n';
    std::cout << one_at_a_time({{0, 86400}, {40000, 40060}}) << '\n';

    // The largest log: 200,000 jobs of 100 seconds each, back to back, listed latest first.
    std::vector<Job> log;
    for (int i = 199'999; i >= 0; --i) log.push_back({100 * i, 100 * i + 100});
    std::cout << one_at_a_time(log) << '\n';
    log[0].first -= 1;  // the latest job now starts 1 second early
    std::cout << one_at_a_time(log) << '\n';
}

package main

import (
	"cmp"
	"fmt"
	"slices"
)

// Job is the half-open interval [Start, End), with Start < End.
type Job struct{ Start, End int }

// oneAtATime reports whether no two jobs overlap.
func oneAtATime(jobs []Job) bool {
	inOrder := slices.Clone(jobs) // sort a copy, so the caller's log keeps its order
	slices.SortFunc(inOrder, func(a, b Job) int {
		return cmp.Or(cmp.Compare(a.Start, b.Start), cmp.Compare(a.End, b.End))
	})
	for i := 1; i < len(inOrder); i++ {
		if inOrder[i].Start < inOrder[i-1].End { // starts before the job before it has ended
			return false
		}
	}
	return true
}

func main() {
	fmt.Println(oneAtATime([]Job{{3600, 5400}, {0, 3600}, {5400, 9000}}))
	fmt.Println(oneAtATime([]Job{{0, 3600}, {7200, 9000}, {3000, 4000}}))
	fmt.Println(oneAtATime([]Job{{0, 86400}, {40000, 40060}}))

	// The largest log: 200,000 jobs of 100 seconds each, back to back, listed latest first.
	log := make([]Job, 0, 200_000)
	for i := 199_999; i >= 0; i-- {
		log = append(log, Job{100 * i, 100*i + 100})
	}
	fmt.Println(oneAtATime(log))
	log[0].Start-- // the latest job now starts 1 second early
	fmt.Println(oneAtATime(log))
}

The Java, C++ and Go versions, compiled and run:

from session import run, versions

# OneAtATime.java runs as a single source file, one_at_a_time.cpp is built with the sanitizers on, and go run builds
# one_at_a_time.go.
versions("java -version", "clang++ --version", "go version")
run("""
java OneAtATime.java
clang++ -std=c++23 -O2 -Wall -Wextra -fsanitize=address,undefined one_at_a_time.cpp -o one_at_a_time && ./one_at_a_time
go run one_at_a_time.go
""")

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java OneAtATime.java
true
false
false
true
false
$ clang++ -std=c++23 -O2 -Wall -Wextra -fsanitize=address,undefined one_at_a_time.cpp -o one_at_a_time && ./one_at_a_time
true
false
false
true
false
$ go run one_at_a_time.go
true
false
false
true
false

All five print the answers for the three example logs, then two answers for the largest log the limits allow: 200,000 jobs of 100 seconds, back to back and listed latest first, which fit, and the same log with its latest job starting one second early, which does not. Each version sorts a copy, so the caller’s log keeps its order: Python’s sorted returns a new list, the JavaScript version spreads the log into a new array, Java clones the array, C++ takes the vector by value, and Go uses slices.Clone. Two of them need care with the sort itself. JavaScript’s sort() without a compare function orders values as text, so the code passes one. Java’s comparator comes from Comparator.comparingInt, which compares by the key itself. A hand-written (x, y) -> x[0] - y[0] looks the same, but int subtraction wraps around without an error when the difference passes 2,147,483,647, and the comparator then gets the order wrong.

Why it is correct

Number the jobs in sorted order, so that their starts satisfy s0 ≤ s1 ≤ … ≤ s(n − 1), and suppose that no neighbours clash: each job has ended by the time the next one starts, e(i) ≤ s(i + 1) for every i. Take any two jobs i and k with i before k. Then e(i) ≤ s(i + 1) ≤ s(k): job i has ended by the time job k starts, so they do not overlap. So when no neighbours clash, no pair does, and the answer True is right. When some neighbours do clash, the later one started while the earlier one was running, and the answer False is right.

That last step needs every job to take time. A job of no length, start equal to end, would count as a clash with any job running across its second, though it holds the server for no time at all. The constraints rule it out here; the exercise below allows it.

Sorting by end works too for this yes-or-no question, which the stress test below checks: mirror the timeline, so that every second t becomes −t, and the order by end, read backwards, becomes an order by start.

A dry run

The first two example logs, sorted by start, neighbour by neighbour:

1. First log, (0, 3600) then (3600, 5400): the next job starts at 3,600 and the one before it ends at 3,600. 3,600 is not before 3,600, so there is no clash.
2. First log, (3600, 5400) then (5400, 9000): 5,400 against 5,400, no clash again, and the log answers True.
3. Second log, (0, 3600) then (3000, 4000): 3,000 is before 3,600, a clash, so the log answers False at once.

The second log’s last pair, (3000, 4000) and (7200, 9000), is never looked at: one clash settles the answer.

The cost

The O(n) extra space is the sorted copy. At the limits, the sort does on the order of n log₂ n, about 200,000 × 18 ≈ 3.6 million comparisons, and the scan 200,000 more, against about 2 × 10¹⁰ pairs for the brute force.

Check it against the brute force

As in the lesson on brute force to optimal, a stress test runs the fast version and the brute force on many small random logs, the shortest first, and stops at the first log where they disagree. It also tries two plausible slips and the version sorted by end:

import random
from itertools import pairwise

from brute import one_at_a_time_brute
from one_at_a_time import one_at_a_time


def with_less_or_equal(jobs):
    """A plausible slip: <= instead of <, so a job that starts in the second another ends counts as a clash."""
    in_order = sorted(jobs)
    for before, after in pairwise(in_order):
        if after[0] <= before[1]:
            return False
    return True


def without_sorting(jobs):
    """Another slip: neighbours in the order of the log, with no sort first."""
    for before, after in pairwise(jobs):
        if before[0] < after[1] and after[0] < before[1]:
            return False
    return True


def sorted_by_end(jobs):
    """Sorted by end instead of start, then the same neighbour check."""
    in_order = sorted(jobs, key=lambda job: job[1])
    for before, after in pairwise(in_order):
        if after[0] < before[1]:
            return False
    return True


def first_failure(candidate, cases=2_000, seed=14):
    """Runs candidate and the brute force on small random logs, shortest first, until they disagree."""
    rng = random.Random(seed)
    for case in range(cases):
        size = 1 + case * 8 // cases  # 1 to 8 jobs
        jobs = []
        for _ in range(size):
            start = rng.randrange(20)
            jobs.append((start, rng.randint(start + 1, 20)))
        got, expected = candidate(jobs), one_at_a_time_brute(jobs)
        if got != expected:
            return f"fails on {jobs}: got {got}, expected {expected}"
    return f"agrees with the brute force on {cases:,} random logs"


for candidate in [one_at_a_time, with_less_or_equal, without_sorting, sorted_by_end]:
    print(f"{candidate.__name__ + ':':<19} {first_failure(candidate)}")

one_at_a_time:      agrees with the brute force on 2,000 random logs
with_less_or_equal: fails on [(11, 18), (18, 20)]: got False, expected True
without_sorting:    fails on [(12, 19), (3, 11), (18, 20)]: got True, expected False
sorted_by_end:      agrees with the brute force on 2,000 random logs

The sorted version agrees on all 2,000 logs, and so does the version sorted by end, as the mirror argument says. The two slips fail quickly. Writing <= for < turns the back-to-back jobs (11, 18) and (18, 20) into a clash. Skipping the sort compares neighbours in the order of the log, and so it misses (12, 19) and (18, 20), which overlap but have another job between them in the log.

Edge cases and common bugs

• A log of one job has no neighbours, so the loop never runs and the answer is True.
• Two jobs that start in the same second always overlap when both take time, so it does not matter which of them the sort puts first.
• Back-to-back jobs must pass: the check is <, never <=, because the convention is half-open.
• Sorting the caller’s list in place, with Python’s list.sort() or Java’s Arrays.sort(jobs), reorders the log the caller still holds. Sort a copy, or ask whether changing the input is allowed.
• Jobs that take no time, if the constraints allowed them, must be dropped before the neighbour check.
• Times that arrive as text must become numbers first, as the section on normalising showed.

Follow-up questions

Which two jobs clashed? Keep each job’s position through the sort, for example by sorting triples (start, end, position), and return the positions of the first neighbours that clash. No clash begins earlier than that one: the jobs before it in sorted order never overlap one another, and every later job starts no earlier.

The times are whole minutes of one day. Does anything change? A day has 1,440 minutes, so at most 1,440 jobs that each take time can run one after another without a clash, and a longer log can answer False at once. With starts limited to 1,440 values, a counting sort by start minute also brings the cost down to O(n + 1,440).

The log grows by one job at a time. Do you sort again for every job? No. Keep the jobs in a structure that stays sorted, and check each new job only against the job that starts just before it and the one that starts just after it. The last lesson of this module builds that with ordered maps.

Intervals in each language

Sorting a copy of the intervals by start is one line in each language, with one thing to watch in each:

• Python: sorted(jobs). Tuples compare by start, then by end, and the Sorting Techniques guide states that Python’s sorts are stable, so records with equal keys keep their order. sorted(jobs, key=lambda job: job[1]) sorts by end.
• JavaScript: [...jobs].sort((x, y) => x[0] - y[0]). Without a compare function, sort() compares values as text.
• Java: Arrays.sort(copy, Comparator.comparingInt(job -> job[0])). A comparator that subtracts can overflow; comparingInt compares the keys.
• C++: std::ranges::sort(jobs) on a vector of std::pair, which compares by first, then second. Take the vector by value to sort a copy.
• Go: slices.SortFunc(c, func(a, b Job) int { return cmp.Compare(a.Start, b.Start) }). SortFunc is not stable; slices.SortStableFunc keeps equal elements in their order.

The overlap test is the same line in every language, and so is the conversion of “H:MM” to minutes: split on the colon and compute hours × 60 + minutes.

Exercise

can_attend_all([("9:30", "10:15"), ("10:15", "11:00"), ("08:00", "9:30")])  # True: they only touch
can_attend_all([("13:00", "14:00"), ("13:45", "14:30")])                   # False: 13:45 to 14:00 is booked twice
can_attend_all([("9:00", "17:00"), ("12:00", "12:00")])                     # True: the second takes no time

def can_attend_all(meetings):
    """True when no two meetings overlap. Each meeting is a pair of times, such as ("9:30", "10:15")."""
    # Replace this line with your code.
    return None

import random

from meetings import can_attend_all


def minutes(text):
    hours, mins = text.split(":")
    return int(hours) * 60 + int(mins)


def every_pair(meetings):
    """A brute force the tests trust: two meetings clash when the later start comes before the earlier end."""
    times = [(minutes(start), minutes(end)) for start, end in meetings]
    for i in range(len(times)):
        for j in range(i + 1, len(times)):
            if max(times[i][0], times[j][0]) < min(times[i][1], times[j][1]):
                return False
    return True


def test_prompt_examples():
    """the three examples of the prompt"""
    assert can_attend_all([("9:30", "10:15"), ("10:15", "11:00"), ("08:00", "9:30")]) is True
    assert can_attend_all([("13:00", "14:00"), ("13:45", "14:30")]) is False
    assert can_attend_all([("9:00", "17:00"), ("12:00", "12:00")]) is True


def test_touching_meetings():
    """meetings that only touch fit; one minute longer and they clash"""
    assert can_attend_all([("11:00", "11:30"), ("09:00", "10:00"), ("10:00", "11:00")]) is True
    assert can_attend_all([("11:00", "11:30"), ("09:00", "10:01"), ("10:00", "11:00")]) is False


def test_hours_without_a_leading_zero():
    """9:45 comes before 10:00 on the clock, though not as text"""
    assert can_attend_all([("9:45", "10:30"), ("10:00", "10:15")]) is False
    assert can_attend_all([("9:59", "10:00"), ("10:00", "10:01")]) is True
    assert can_attend_all([("8:00", "9:00"), ("10:00", "11:00"), ("9:00", "10:00")]) is True


def test_one_meeting_inside_another():
    """a short meeting inside a long one, in either order"""
    assert can_attend_all([("08:00", "18:00"), ("12:30", "13:00")]) is False
    assert can_attend_all([("12:30", "13:00"), ("08:00", "18:00")]) is False


def test_end_of_the_day():
    """24:00 is the end of the day, 1440 minutes after midnight"""
    assert can_attend_all([("23:00", "24:00"), ("00:00", "01:00")]) is True
    assert can_attend_all([("22:30", "24:00"), ("23:45", "23:50")]) is False
    assert can_attend_all([("23:30", "24:00"), ("24:00", "24:00")]) is True


def test_meetings_that_take_no_time():
    """a meeting that starts and ends in the same minute overlaps nothing"""
    assert can_attend_all([("12:00", "12:00"), ("9:00", "17:00")]) is True
    assert can_attend_all([("10:00", "10:00"), ("10:00", "10:00")]) is True
    assert can_attend_all([("10:00", "10:00"), ("9:30", "10:30"), ("10:15", "10:45")]) is False


def test_empty_sheet_and_one_meeting():
    """no meetings, or one, always fit"""
    assert can_attend_all([]) is True
    assert can_attend_all([("9:00", "9:30")]) is True


def test_input_unchanged():
    """the caller's list keeps its order"""
    sheet = [("10:00", "11:00"), ("9:00", "9:30"), ("12:00", "12:00")]
    can_attend_all(sheet)
    assert sheet == [("10:00", "11:00"), ("9:00", "9:30"), ("12:00", "12:00")]


def test_against_brute_force():
    """300 random sheets: the same answer as a trusted brute force"""
    rng = random.Random(14)
    slots = [*range(480, 721, 15), *range(1380, 1441, 15)]  # 8:00 to 12:00 and 23:00 to 24:00, every 15 minutes

    def as_text(minute):
        hours, mins = divmod(minute, 60)
        return f"{hours:02d}:{mins:02d}" if rng.random() < 0.5 else f"{hours}:{mins:02d}"

    for _ in range(300):
        sheet = []
        for _ in range(rng.randint(0, 6)):
            start = rng.choice(slots)
            end = start if rng.random() < 0.15 else rng.choice([s for s in slots if s >= start])
            sheet.append((as_text(start), as_text(end)))
        assert can_attend_all(sheet) is every_pair(sheet), f"can_attend_all({sheet})"

Interview questions

How do you test whether two intervals overlap, and how does the test change between half-open and closed intervals? Two non-empty half-open intervals [a1, b1) and [a2, b2) overlap exactly when each starts before the other ends: a1 < b2 and a2 < b1. It comes from the opposite case: they are disjoint when one ends no later than the other starts, b1 <= a2 or b2 <= a1, and negating that gives the test. For closed intervals, touching at one point already counts, so the test is a1 <= b2 and a2 <= b1. An equivalent form, max(a1, a2) < min(b1, b2), also gives the shared part and says “no overlap” whenever either interval is empty. The usual bug is checking only whether one interval’s endpoints fall inside the other, which misses an interval that contains the other with room on both sides, such as [1, 2) inside [0, 3).

What is the difference between a closed and a half-open interval, and which would you use for meeting times? A closed interval [a, b] contains both endpoints; a half-open interval [a, b) contains its start but not its end. For meetings, use half-open: a meeting from 9:00 to 10:00 and one from 10:00 to 11:00 then share no minute, so back-to-back meetings never count as a clash. Half-open intervals also have the length b - a, meet without a gap or an overlap, and write an empty interval as [a, a). Calendars agree: iCalendar defines an event’s end as non-inclusive. Closed intervals suit counts of whole units, such as days 3 to 7 inclusive, and convert to half-open by adding one to the end: [3, 8).

Key takeaways

• A closed interval [a, b] holds both ends; a half-open interval [a, b) holds its start but not its end.
• Use half-open intervals for times and indices: the length is b - a, and back-to-back intervals do not overlap.
• Two non-empty half-open intervals overlap when a1 < b2 and a2 < b1; closed ones when both comparisons are <=.
• max(a1, a2) < min(b1, b2) is the same test, also correct when an interval is empty.
• Checking only whether one interval’s endpoints lie inside the other misses containment.
• Normalise first: clock times to minutes, swapped or overnight ends by the problem’s rule, empty intervals decided.
• Sort by start to merge or find a clash; sort by end to keep the most non-overlapping intervals.
• After sorting by start, a clash between any two jobs shows up between neighbours: O(n log n) instead of O(n²).