Meeting Rooms: Interval Overlap

Two intervals overlap when each one starts before the other one ends. Written as start of the first less than end of the second and start of the second less than end of the first. The condition has to be written as two strict inequalities rather than one inclusive comparison, and the reason is the edge case.

Consider a meeting from ten to eleven and another from eleven to twelve. They do not clash, because one ends exactly when the other begins. With inclusive comparisons you would call that an overlap and reject a schedule that is actually fine. With strict comparisons the two conditions are eleven less than eleven, which is false, so the intervals are correctly reported as compatible.

The mechanism is the half open interval convention, treating every interval as start inclusive and end exclusive. That mirrors how time actually behaves in a calendar: a booking that ends at eleven hands the room over at eleven, and the next booking starts at that same instant. Under that convention, two intervals conflict exactly when they share a positive amount of time.

The trade-off to name is that the strict version breaks if the problem defines a meeting as inclusive of its end time, so the convention should be stated before the code is written. In a scheduling system the same logic decides whether two jobs can use one machine, and it is the same function. When you have many bookings rather than two, sorting them by start time and comparing each one against the previous is the standard extension, and it costs O of n log n to sort plus a linear scan.

Compare the two starts against the two ends. The intervals conflict only when the first starts before the second ends and the second starts before the first ends, both strictly.

def overlaps(a, b):
    start_a, end_a = a
    start_b, end_b = b
    return start_a < end_b and start_b < end_a


print(overlaps((1, 5), (4, 8)))
print(overlaps((1, 3), (4, 8)))

The outputs are True and False. The first pair runs from one to five and from four to eight, so they share the hour from four to five. The second pair has a clear gap between three and four.

The mechanism is the conjunction of the two conditions. The first condition says the second interval starts before the first one finishes, and the second says the first interval starts before the second one finishes. Both have to hold for there to be shared time, and either one failing means one of the intervals lies entirely outside the other.

The trade-off to name is the strictness. With strict comparisons, a meeting ending at eleven and another starting at eleven are compatible, which matches how calendars behave. If the problem instead treats a meeting as including its final minute, then a booking that ends at eleven clashes with one that starts at eleven, and the condition becomes less than or equal on both sides. Saying which convention you are using is the important part of the answer, and it takes one sentence.