Skip to main content

Online Bookings

Trigger: bookings arrive one at a time and each needs an answer before the next. The input is not all there yet, so keep a structure that stays sorted (a sorted list, or a sorted map of +1/-1 events) and answer against it. The other pages see the whole list at once. Which question is it asking?

Binary search on intervals​

The other interval techniques walk the whole list. Once the list is sorted, though, a single question asked about it - "which stored intervals does this new one touch?", "how many are live at this instant?" - should not cost a full pass. Binary search is what turns those into O(log n), and the surprise is that it needs no new idea: it is doesIntersect from the index, read one more time.

You never binary search over pairs​

bisect needs a sorted array of comparable scalars, and a list of [start, end] pairs is not that. So the first move is always the same - project the intervals onto two scalar arrays and search those:

starts = [i[0] for i in intervals]
ends = [i[1] for i in intervals]

starts is sorted because the list is sorted by start. ends is sorted only if the list is also disjoint, and that one condition splits this whole section in two.

Take a list that is sorted and non-overlapping, and a query interval q (q = [q0, q1], the new interval being asked about). Ask the overlap test of every stored interval in turn:

doesIntersect(intervals[i], q) = ends[i] >= q0 and starts[i] <= q1

Now look at each half as i runs left to right. ends ascends, so ends[i] >= q0 is false, false, false, then true and stays true. starts ascends, so starts[i] <= q1 is true, true, true, then false and stays false. Neither flips back. A predicate that flips exactly once over a sorted array is precisely what bisect locates the boundary of, so each half costs one binary search:

from bisect import bisect_left, bisect_right
 
firstTouching = lambda ends, q: bisect_left(ends, q[0]) # first i with ends[i] >= q0
afterLastTouching = lambda starts, q: bisect_right(starts, q[1]) # one past the last i with starts[i] <= q1

The and joining the two halves becomes an intersection of ranges, and since one is a suffix [lo, n) and the other a prefix [0, hi), the result is the half-open slice [lo, hi):

071627query q = [7,16][1,3]✗ ends[i] >= q0✓ starts[i] <= q1[5,8]✓ ends[i] >= q0✓ starts[i] <= q1[10,12]✓ ends[i] >= q0✓ starts[i] <= q1[15,18]✓ ends[i] >= q0✓ starts[i] <= q1[20,25]✓ ends[i] >= q0✗ starts[i] <= q1intervals[lo:hi], lo=1, hi=4
Intervals [1,3], [5,8], [10,12], [15,18], [20,25] against the query q = [7,16], drawn as the shaded band. The left column turns on at i=1 and never turns off; the right column turns off at i=4 and never turns on. Their overlap, rows 1 to 3, is exactly the set of bars the band touches.

intervals[lo:hi] is exactly the set that intersects q, and everything below is a different question asked about that one slice. An empty slice (lo == hi) means nothing was touched.

The closed/strict choice crosses over again​

bisect_left and bisect_right differ only on where they place a value equal to an existing element, which is the same decision > versus >= makes on a shared endpoint. So the convention table from isInGap has a binary-search column, and it crosses over the same way:

ConventionOverlap testlo = firstTouchinghi = afterLastTouching
Closed - merging, coveragedoesIntersect (>=)bisect_left(ends, q0)bisect_right(starts, q1)
Half-open - schedulingdoesIntersectStrictly (>)bisect_right(ends, q0)bisect_left(starts, q1)

Under the closed row a stored interval ending exactly at q0 is pulled into the slice; under the half-open row it is left out, because a meeting ending at 10:00 does not conflict with one starting at 10:00. Pick the row, not the function name.

When the list overlaps: depth by two independent searches​

Drop the disjoint requirement and ends stops being sorted, which kills both searches above. The repair is to give up the pairing entirely: sort starts and ends as two independent arrays, and count instead of locate.

countStarted = lambda starts, t: bisect_right(starts, t) # how many have begun by t
countFinished = lambda ends, t: bisect_left(ends, t) # how many are already over
depthAt = lambda starts, ends, t: countStarted(starts, t) - countFinished(ends, t)

This is the depth of the sweep line, with the sweep removed. The sweep maintains depth incrementally and therefore has to visit the events in order; this computes depth at any single t in O(log n) with no ordering requirement at all, so the queries may arrive shuffled and each is answered on its own.

5t = 5[1,6][3,7][4,13][9,12]1349startsbisect_right(starts, 5) = 3671213endsbisect_left(ends, 5) = 0depth = 3 - 0 = 3
Four overlapping intervals, so ends is not sorted in list order and the slice primitive does not apply. Sorting starts and ends separately still answers 'how many contain t = 5': three have begun, none have finished.

"Started minus finished" survives the lost pairing because every interval falls into exactly one of three buckets at time t: not yet begun (counted by neither term), already over (counted by both, so it cancels), or live (counted by the first only). Which start belongs to which end never enters the arithmetic.

One catch: bisect_left(ends, t) counts ends strictly before t, so here an interval ending at t still counts as live. Use bisect_right(ends, t) for the half-open depth defined on Line Sweeps.

GOTCHAends is sorted only when the list is disjoint

Choosing between the two​

Three questions, in order:

  1. Is the list disjoint? Use the slice. intervals[lo:hi] is the touched set, and hi - lo answers most of the rest.
  2. Not disjoint, but only a count at a point is needed? Use depth. Two independent arrays, two bisect calls.
  3. Not disjoint, and you need to know which interval? Binary search can only narrow the candidates - a heap or a max-end segment tree picks the winner among them.
QuestionPrimitiveExpression
Does a new interval conflict with any stored one?slicehi - lo == 0
Where does a new interval merge in?sliceintervals[:lo] + [merged] + intervals[hi:]
Is a query range fully covered?slice + doesContainhi - lo == 1 and doesContain(intervals[lo], q)
Which stored interval contains this point?slice with q0 == q1lo if lo < hi else none
How many intervals are live at this instant?depthcountStarted(t) - countFinished(t)

The two primitives never do the judging themselves. They locate a candidate, and doesContain, getMerged, doesIntersect - the primitives from the index - decide what it means. That composition is the pattern: bisect narrows, the interval primitives judge.

Bookings one at a time​

Intervals arrive one by one and each must be answered before the next, so there is no sorting up front. Keep a structure that stays sorted as bookings land - a sorted list with bisect, or a running map of +1/-1 events - and answer against it.

729. My Calendar I​

729

My Calendar I

LeetCode
Medium

Sorted List with Sentinel Gap Scan

FIG. 729 MY CALENDAR I● INTERACTIVE
visualization loads as you reach it
class MyCalendar:
 
def __init__(self):
self.intervals = [[-1, -1]]
 
def book(self, startTime: int, endTime: int) -> bool:
doesIntersectStrictly = lambda a, b: (a[1] > b[0] and b[1] > a[0])
isInGap = lambda left, right, a: a[0] >= left[1] and a[1] <= right[0]
newInterval = [startTime, endTime]
 
for i in range(1, len(self.intervals)):
if isInGap(self.intervals[i - 1], self.intervals[i], newInterval):
self.intervals.insert(i, newInterval)
return True
if doesIntersectStrictly(self.intervals[i], newInterval):
return False
self.intervals.append(newInterval)
return True
 
 
# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(startTime,endTime)
top ↑

731. My Calendar II​

731

My Calendar II

LeetCode
Medium

Speculative Event Insert with Revert

FIG. 731 MY CALENDAR II● INTERACTIVE
visualization loads as you reach it
import sortedcontainers
 
 
class MyCalendarTwo:
 
def __init__(self):
self.line = sortedcontainers.SortedDict()
 
def book(self, startTime: int, endTime: int) -> bool:
self.line[startTime] = self.line.get(startTime, 0) + 1
self.line[endTime] = self.line.get(endTime, 0) - 1
active = 0
for point, curr in self.line.items():
active += curr
if active > 2:
self.line[startTime] -= 1
self.line[endTime] += 1
return False
return True
 
 
# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(startTime,endTime)
top ↑

732. My Calendar III​

732

My Calendar III

LeetCode
Hard

Persistent Sweep for the Running Peak

FIG. 732 MY CALENDAR III● INTERACTIVE
visualization loads as you reach it
from sortedcontainers import SortedDict
 
 
class MyCalendarThree:
 
def __init__(self):
self.line = SortedDict()
 
def book(self, startTime: int, endTime: int) -> int:
self.line[startTime] = self.line.get(startTime, 0) + 1
self.line[endTime] = self.line.get(endTime, 0) - 1
active = maxi = 0
for point, curr in self.line.items():
active += curr
maxi = max(maxi, active)
return maxi
 
 
# Your MyCalendarThree object will be instantiated and called as such:
# obj = MyCalendarThree()
# param_1 = obj.book(startTime,endTime)
top ↑

352. Data Stream as Disjoint Intervals​

352

Data Stream as Disjoint Intervals

LeetCode
Hard

Re-Merge the Whole List on Every Insert

FIG. 352 DATA STREAM AS DISJOINT INTERVALS● INTERACTIVE
visualization loads as you reach it
class SummaryRanges:
 
def __init__(self):
self.intervals = []
 
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: (a[1] >= b[0] and b[1] >= a[0])
 
merged = []
for inter in intervals:
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
merged.append(inter)
return merged
 
def addNum(self, value: int) -> None:
self.intervals.append((value, value + 1))
self.intervals = self.merge(self.intervals)
 
def getIntervals(self) -> list[list[int]]:
return [[i, j - 1] for i, j in self.intervals]
 
 
# Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(value)
# param_2 = obj.getIntervals()
top ↑

2276. Count Integers in Intervals​

2276

Count Integers in Intervals

LeetCode
Hard

Merge on Insert, Length Computed in the Same Pass

FIG. 2276 COUNT INTEGERS IN INTERVALS MERGE● INTERACTIVE
visualization loads as you reach it
class CountIntervals:
def __init__(self):
self.intervals = []
self.len = 0
 
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: (a[1] >= b[0] and b[1] >= a[0])
 
merged = []
self.len = 0
for inter in intervals:
if merged and doesIntersect(merged[-1], inter):
self.len -= merged[-1][1] - merged[-1][0] + 1
merged[-1] = getMerged(merged[-1], inter)
self.len += merged[-1][1] - merged[-1][0] + 1
else:
self.len += inter[1] - inter[0] + 1
merged.append(inter)
return merged
 
def add(self, left: int, right: int) -> None:
idx = bisect.bisect_left(self.intervals, left, key=lambda i: i[0])
self.intervals.insert(idx, (left, right))
self.intervals = self.merge(self.intervals)
 
def count(self) -> int:
return self.len
top ↑
On this page