Introduction
Intervals are simply pairs of integers. [1,2], [3,6]. They can represent time ranges that you are free or busy on a calendar, or even distances between objects in space. Many of these problems you encounter involving intervals result from modelling real-world situations, so it is even more crucial to understand this topic well – not just for interviews, but for your career.
Examples:
- Meeting room scheduling
- Task planning
- Resource allocation
- Time series analysis
- Traffic control systems
The key insight to solving interval problems efficiently is proper sorting and greedy algorithms. Most interval problems become much simpler when you first sort the intervals based on start points or end points.
Visual Representation:
Intervals on a number line:
[----]
[----]
[------]
[--]
[--]Each line segment represents an interval [start, end]. Note that there are 4 cases, and it's important to be careful. [s,e], (s,e), (s,e], [s,e). Open parenthesis means non-inclusive and closed parenthesis means inclusive of that endpoint. It's important to know what defines overlap as well, for example do [1,2] and [2,3] overlap? Some questions consider that as overlap and some questions don't. Read the question carefully.
Allen's Interval Algebra
The way I like to think about it: fix the second interval B. Imagine sliding the first interval A from left to right.
Consider two intervals A = [a,b] and B = [c,d] on a number line. Here are the possible situations:
1. A before B:
[a---b]
[c---d]
2. A meets B:
[a---b]
[c---d]
3. A overlaps B:
[a------b]
[c------d]
4. A starts B:
[a-----b]
[c---------d]
5. A during B:
[a-----b]
[c---------d]
6. A finishes B:
[a-----b]
[c---------d]
7. A is leaving B:
[a-----b]
[c---------d]
8. A left B:
[a-----b]
[c---------d]
9. B before A (inverse of 1)
[a---b]
[c---d]
10. A equals B:
[a---------b]
[c---------d]
11. A contains B:
[a-----------b]
[c-----d]The beauty of interval algebra is that we can distill the detection of any overlap (relations 2-8, and 10-11) into a single elegant formula:
Two intervals [a,b] and [c,d] overlap if and only if: max(a,c) ≤ min(b,d)
When this condition is true, the overlapping segment is exactly [max(a,c), min(b,d)].
Think about:
[ ]
[ ][a,b] and [c,d]
The overlap is: max on the left of the two starts and min on the right of the two ends.
And the only two other cases are 1 and 9, where there is no overlap between the 2 intervals.
Basic Interval Problems
Fundamental interval problems including merging and counting gaps.
01Merge IntervalsMedium
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example:
- Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
- Output: [[1,6],[8,10],[15,18]]
- Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
res = []
for s, e in intervals:
if res and s <= res[-1][1]:
res[-1][1] = max(res[-1][1], e)
else:
res.append([s, e])
return res
# Alternative using overlap formula
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
res = []
for s, e in intervals:
if res and max(s, res[-1][0]) <= min(e, res[-1][1]):
res[-1][1] = max(res[-1][1], e)
else:
res.append([s, e])
return resO(n log n)O(n)We sort the intervals by start time, and then iterate. If the current segment starts before the end of the current segment (the last one in res) then we overlap, and so we can extend the current segment in res. Otherwise, if there is no overlap (case 9) we are starting a new segment and can safely add this new segment to res.
02Count Days Without MeetingsMedium
You are given a positive integer days representing the total number of days an employee is available for work (starting from day 1). You are also given a 2D array meetings of size n where, meetings[i] = [start_i, end_i] represents the starting and ending days of meeting i (inclusive).
Return the count of days when the employee is available for work but no meetings are scheduled.
Example:
- Input: days = 10, meetings = [[5,7],[1,3],[9,10]]
- Output: 2
- Explanation: There is no meeting scheduled on the 4th and 8th days.
def countDays(self, days: int, meetings: List[List[int]]) -> int:
res = day = 0
for s, e in sorted(meetings):
res += max(0, s - day - 1)
day = max(day, e)
return res + (days - day)O(n log n)O(1)The easiest explanation is to walk through the example. Sorting meeting gives [1,3], [5,7], [9,10].
We basically want to count the gaps of days between meetings. This is what max(0, s-day-1) does. S-day-1 can be negative because the intervals can overlap. Also the case where the current end time is less than the previous end time (day) is possible, think about [1,6], [2,3], so we need to take the max, to keep day = 6. Don't forget about the last gap days - day.
Meeting Rooms Problems
Classic meeting room scheduling problems.
01Meeting RoomsEasy
Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.
Example 1:
- Input: intervals = [[0,30],[5,10],[15,20]]
- Output: false
Example 2:
- Input: intervals = [[7,10],[2,4]]
- Output: true
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
for (a, b), (c, d) in pairwise(sorted(intervals)):
if max(a, c) < min(b, d):
return False
return True
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
return not any(max(a, c) < min(b, d) for (a, b), (c, d) in pairwise(sorted(intervals)))O(n log n)O(sort)Basically just consider all pairwise intervals, and check if there is overlap. (note: touching is not considered overlap in this case. Ie. [1,2], [2,3] are NOT overlapping) If there is overlap: ie. max(a,c) < min(b,d), then the user cannot attend all meetings, otherwise if there is no overlap between any pairwise meetings they can attend all meetings.
02Meeting Rooms IIMedium
Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.
Example 1:
- Input: intervals = [[0,30],[5,10],[15,20]]
- Output: 2
# Heap solution
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
heap = [] # min heap of end times
for a, b in sorted(intervals):
if heap and a >= heap[0]: heappop(heap)
heappush(heap, b)
return len(heap)
# Line sweep solution
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
lines = defaultdict(int)
for a, b in intervals:
lines[a] += 1
lines[b] -= 1
res = 0
acc = 0
for s in sorted(lines):
acc += lines[s]
res = max(res, acc)
return resO(n log n)O(n)Basically we maintain a min heap of earliest current active meeting end times. If this meeting start time is after the earliest meeting end, that means that meeting is done and we can remove it from the heap. Otherwise, we want to add this meeting as currently active. At the end, the number of currently active meetings is the answer.
Note: we can solve Meetings Room I using this algorithm, and checking if the minMeetingRooms == 1.
Interval Intersection
Problems involving finding intersections between interval lists.
01Interval List IntersectionsMedium
You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.
Return the intersection of these two interval lists.
def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
m, n = len(firstList), len(secondList)
i = j = 0
res = []
while i < m and j < n:
a, b = firstList[i]
c, d = secondList[j]
overlap = max(a, c) <= min(b, d)
if overlap:
res.append([max(a, c), min(b, d)])
if b < d:
i += 1
else:
j += 1
return resO(m + n)O(m + n)We just do two pointers, if there is overlap add it. The interesting part is how do we decide to increment which pointer. This is completely greedy logic. The one that ends later serves more utility for us, because it provides more opportunity for future intersection, so let's keep it and discard the other.
Ie. [1,10] vs [2,5], [6,8]. Discarding [2,5] is the right choice, because later the [6,8] will intersect again with [1,10].
If we instead chose to discard based on earlier start time, then we would completely miss this [6,8] intersection.
It's important to be able to think ahead, and come up and reason about these edge cases before presenting your solution to your interviewer.
Removing Intervals
Problems involving removing or modifying intervals.
01Remove Covered IntervalsMedium
Given an array intervals where intervals[i] = [li, ri] represent the interval [li, ri), remove all intervals that are covered by another interval in the list.
The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.
Return the number of remaining intervals.
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
# Sort by start point.
# If two intervals share the same start point
# put the longer one to be the first.
intervals.sort(key=lambda x: (x[0], -x[1]))
count = 0
prev_e = 0
for _, e in intervals:
# if current interval is not covered by the previous one
if prev_e < e:
count += 1
prev_e = e
return countO(n log n)O(1)We need to sort carefully, first by starting time but if there is a tie then take the one with longer end time first. The intuition is we want all covered intervals to appear after the supersetting interval. Ie. [[1,2],[1,4],[3,4]] should be [[1,4],[1,2],[3,4]]
Now, iterating over intervals: if the previous end time >= current end time, this means the current interval is covered by the previous because the current interval start time is >= the previous intervals start time as well. (intervals is sorted) Otherwise, this current interval is not covered by the previous, so we update our count of remaining intervals and update the end time.
02Remove IntervalMedium
You are given a sorted list of disjoint intervals intervals representing a set of real numbers, where intervals[i] = [ai, bi] represents the interval [ai, bi). You are also given another interval toBeRemoved.
Return the set of real numbers with the interval toBeRemoved removed from intervals.
def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
c, d = toBeRemoved
res = []
for a, b in intervals:
overlap = max(a, c) < min(b, d)
if overlap:
first = [a, max(a, c)] # before overlap
second = [min(b, d), b] # after overlap
for x, y in [first, second]:
if x < y:
res.append([x, y])
else:
res.append([a, b])
return resO(n)O(n)This should be fairly straightforward, just look at the 3 examples. If there is no overlap, add the segment. If there is overlap, then we have 3 segments: the one before overlap, the overlap, and the one after overlap. If any of them are not single points, we add them to res. (it's possible the segment is like [5,5] for example)
03Insert IntervalMedium
You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end].
Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return intervals after the insertion.
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
res = []
for s, e in intervals:
if res and s <= res[-1][1]:
res[-1][1] = max(res[-1][1], e)
else:
res.append([s, e])
return res
# Linear scan
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
i = 0
n = len(intervals)
c, d = newInterval
while i < n and intervals[i][1] < c:
i += 1
j = n - 1
while j >= 0 and d < intervals[j][0]:
j -= 1
merged = self.merge(intervals[i:j+1] + [newInterval])
return intervals[:i] + merged + intervals[j+1:]
# Binary search
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
l, r = newInterval
i = bisect_right(intervals, [l, inf]) - 1
j = bisect_left(intervals, [r+1, -inf]) - 1
i = max(0, i)
merged = self.merge(intervals[i:j+1] + [newInterval])
return intervals[:i] + merged + intervals[j+1:]O(n)O(n)The key is to realize that there are 3 ranges to the answer. The first list of intervals that don't overlap to the left of the inserted one. The list of intervals in the middle that overlap with the inserted one, that we have to merge together. And the list of intervals to the right that don't overlap. Now the question is, what are these indices i,j that define this middle list of intervals that overlap?
There's two ways. First is a linear scan to find starting i and ending j indices that define the range we should merge. Second is using binary search.
Both are O(n) time and space. You might wonder why we would use binary search if the complexity is the same? Look at the Count Integers in Intervals question :)
04Count Integers in IntervalsHard
Given an empty set of intervals, implement a data structure that can:
- Add an interval to the set of intervals.
- Count the number of integers that are present in at least one interval.
Implement the CountIntervals class:
- CountIntervals() Initializes the object with an empty set of intervals.
- void add(int left, int right) Adds the interval [left, right] to the set of intervals.
- int count() Returns the number of integers that are present in at least one interval.
from sortedcontainers import SortedList
class CountIntervals:
def __init__(self):
self.res = 0
self.intervals = SortedList()
# looks like O(n + logn) time per add, BUT CONSIDER AMORTIZED ANALYSIS!!!
# can only pop every added interval ONCE...
# O(1 + logn) amortized for the binary search...
def add(self, left: int, right: int) -> None:
j = self.intervals.bisect_left((right+1, -inf)) - 1
while j >= 0 and max(left, self.intervals[j][0]) <= min(right, self.intervals[j][1]):
left = min(left, self.intervals[j][0])
right = max(right, self.intervals[j][1])
self.res -= self.intervals[j][1] - self.intervals[j][0] + 1
self.intervals.pop(j)
j -= 1
self.intervals.add((left, right))
self.res += right - left + 1
def count(self) -> int:
return self.resO(log n) amortized per addO(n)Notice the similarities with insert interval. This is a hard problem that is instantly trivialized if you understand the insert interval problem carefully.
Line Sweep Technique
After mastering the basic interval problem patterns, let's dive into a powerful technique that solves a wide range of interval challenges: the line sweep algorithm (also known as sweep line).
What is the Line Sweep Algorithm?
The line sweep algorithm processes events in sorted order, "sweeping" a vertical line from left to right across all interval endpoints. At each point, we update our understanding of the current state and compute results based on that state.
Line sweep is particularly effective when dealing with:
- Counting overlapping intervals
- Finding the maximum number of concurrent intervals
- Computing aggregate statistics at different points
- Efficiently handling a mix of intervals and point queries
Visual Representation
Consider the example of finding the max number of overlapping intervals at any point in time.
[1,3], [2,5], [5,7]
+ -
+ -
+ -
1234567Now a running sum (prefix sum) will give:
1211110
1234567This provides a map from timestamp -> running sum, where the running sum represents the number of active intervals at that timestamp. So taking the max prefix sum will give the maximum number of overlapping intervals.
Each interval has a start event (+) and an end event (-). As the sweep line encounters these events, we update our state accordingly.
Important: It's important to be careful with where we put the end minus, is it at e or e+1? This depends on what we consider overlap.
If [1,5], [5,10] are considered overlapping, then you need to update lines[e+1] -= 1.
Otherwise if they are not overlapping, you need to update lines[e] -= 1.
Line Sweep Template
from collections import defaultdict
def lineSweepTemplate(intervals):
# Create events dictionary
events = defaultdict(int)
for start, end in intervals:
events[start] += 1 # Increment counter at start
events[end] -= 1 # Decrement counter at end
# Process events in sorted order
active = 0
result = 0 # or any other tracking variable
for time in sorted(events.keys()):
active += events[time]
# Update result based on active count
result = max(result, active)
return result01Divide Intervals Into Minimum Number of GroupsMedium
You are given a 2D integer array intervals where intervals[i] = [lefti, righti] represents the inclusive interval [lefti, righti].
You have to divide the intervals into one or more groups such that each interval is in exactly one group, and no two intervals that are in the same group intersect each other.
Return the minimum number of groups you need to make.
Two intervals intersect if there is at least one common number between them. For example, the intervals [1, 5] and [5, 8] intersect.
# Heap solution (same as Meeting Rooms II)
def minGroups(self, intervals: List[List[int]]) -> int:
intervals.sort()
group_end_times = []
for s, e in intervals:
if group_end_times and s > group_end_times[0]:
heappop(group_end_times)
heappush(group_end_times, e)
return len(group_end_times)
# Line sweep solution
def minGroups(self, intervals: List[List[int]]) -> int:
lines = defaultdict(int)
for s, e in intervals:
lines[s] += 1
lines[e+1] -= 1
res = 0
sum_ = 0
for t in sorted(lines):
sum_ += lines[t]
res = max(res, sum_)
return resO(n log n)O(n)Key insight: The minimum number of groups needed equals the maximum number of overlapping intervals at any point, which we can efficiently calculate using line sweep.
This is exactly the same as meeting rooms 2, the only difference is we need to subtract 1 at e+1 instead of e. This is because: "Two intervals intersect if there is at least one common number between them. For example, the intervals [1, 5] and [5, 8] intersect."
02Number of Flowers in Full BloomHard
You are given a 0-indexed 2D integer array flowers, where flowers[i] = [starti, endi] means the ith flower will be in full bloom from starti to endi (inclusive). You are also given a 0-indexed integer array people of size n, where people[i] is the time that the ith person will arrive to see the flowers.
Return an integer array answer of size n, where answer[i] is the number of flowers that are in full bloom when the ith person arrives.
# Line sweep solution
def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
people = [(p, i) for i, p in enumerate(people)]
people.sort()
lines = defaultdict(int)
for s, e in flowers:
lines[s] += 1
lines[e+1] -= 1
line_keys = sorted(lines)
idx = 0
cum_sum = 0
res = [-1] * len(people)
for p, i in people:
while idx < len(line_keys) and line_keys[idx] <= p:
cum_sum += lines[line_keys[idx]]
idx += 1
res[i] = cum_sum
return res
# Heap solution
def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
flowers.sort()
sorted_people = sorted(people)
dic = {}
active_flowers = []
i = 0
for person in sorted_people:
while i < len(flowers) and flowers[i][0] <= person:
heapq.heappush(active_flowers, flowers[i][1])
i += 1
while active_flowers and active_flowers[0] < person:
heapq.heappop(active_flowers)
dic[person] = len(active_flowers)
return [dic[x] for x in people]O((n + m) log (n + m))O(n + m)This is pretty simple. Just do the line sweep and simulate. We accumulate all the flowers up until this person p in lines, and that is the number of active flowers that person can see.
You can also do this with a min heap, in a very similar logic. Just maintain a heap of active flowers end times. At the beginning we add all flowers who start before this person time. And we pop all the flowers that ended before this persons time. The remaining flowers in the heap are all the ones that started before this person and ended after this person.
My Calendar Series
The My Calendar series is a perfect showcase for line sweep techniques, demonstrating how to track overlapping events with increasing complexity.
(note SortedDict() just a dictionary with sorted keys. It is useful for sweep line in this case.)
01My Calendar IMedium
You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.
A double booking happens when two events have some non-empty intersection.
Implement the MyCalendar class:
- MyCalendar() Initializes the calendar object.
- boolean book(int startTime, int endTime) Returns true if the event can be added without causing a double booking.
# 1. Brute force O(n) per book
class MyCalendar:
def __init__(self):
self.calendar = []
def book(self, start, end):
for s, e in self.calendar:
if max(s, start) < min(e, end):
return False
self.calendar.append((start, end))
return True
# 2. Binary search O(log n) per book
from sortedcontainers import SortedList
class MyCalendar:
def __init__(self):
self.calendar = SortedList()
def book(self, start, end):
i = bisect_left(self.calendar, (end, float('-inf')))
if i == 0 or self.calendar[i-1][1] <= start:
self.calendar.add((start, end))
return True
return False
# 3. Line sweep O(n) per book - GENERALIZES TO MY CALENDAR II AND III
from sortedcontainers import SortedDict
class MyCalendar:
def __init__(self):
self.lines = SortedDict()
def book(self, start, end):
curr_sum = 0
if start not in self.lines: self.lines[start] = 0
if end not in self.lines: self.lines[end] = 0
self.lines[start] += 1
self.lines[end] -= 1
for time in self.lines:
curr_sum += self.lines[time]
if curr_sum == 2: # overlap
self.lines[start] -= 1
self.lines[end] += 1
if self.lines[start] == 0: del self.lines[start]
if self.lines[end] == 0: del self.lines[end]
return False
return TrueO(n) for line sweep, O(log n) for binary searchO(n)3 solutions: 1. Brute force. O(n). 2. Binary Search. O(logn). 3. Line Sweep. O(n).
Binary search is actually the most efficient, where we find exactly which booking can be overlapping.
However, I recommend learning approach 3, because it will generalize to My Calendar II and III.
Key insight: We use line sweep to count active events at each point. If at any point we have more than one active event, there's an overlap.
02My Calendar IIMedium
Implement a MyCalendarTwo class where double booking is allowed, but triple booking is not.
from sortedcontainers import SortedDict
class MyCalendarTwo:
def __init__(self):
self.lines = SortedDict()
def book(self, start, end):
curr_sum = 0
if start not in self.lines: self.lines[start] = 0
if end not in self.lines: self.lines[end] = 0
self.lines[start] += 1
self.lines[end] -= 1
for time in self.lines:
curr_sum += self.lines[time]
if curr_sum == 3: # ONLY CHANGE THIS FROM 2 TO 3
self.lines[start] -= 1
self.lines[end] += 1
if self.lines[start] == 0: del self.lines[start]
if self.lines[end] == 0: del self.lines[end]
return False
return TrueO(n)O(n)This is similar to MyCalendar I, but now we allow the active count to reach 2 (double booking) but not 3 (triple booking). We only need to change 1 number! This is the power of template/generic based solutions. Understand 1 concept to solve many problems.
03My Calendar IIIHard
Implement a MyCalendarThree class that accepts all bookings and returns the maximum k-booking (the maximum number of overlapping events).
from sortedcontainers import SortedDict
class MyCalendarThree:
def __init__(self):
self.lines = SortedDict()
def book(self, start, end):
curr_sum = 0
if start not in self.lines: self.lines[start] = 0
if end not in self.lines: self.lines[end] = 0
self.lines[start] += 1
self.lines[end] -= 1
res = 0
for time in self.lines:
curr_sum += self.lines[time]
res = max(res, curr_sum)
return resO(n)O(n)Unlike the previous problems, we accept all bookings and simply return the maximum number of concurrent events after each booking. This is a 'hard' problem, but I would classify it as an easy if you read this chapter :)
Skyline Problem
Bonus hard problem combining sweep line with sorted data structures.
01The Skyline ProblemHard
Given the coordinates of buildings as triplets [left, right, height], return the key points of the skyline formed by these buildings.
Example:
- Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
- Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
from sortedcontainers import SortedList
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
# Create special events: (position, height, type)
# Type: 0 for start, 1 for end
events = []
for left, right, height in buildings:
# Start event: negative height to prioritize starts over ends at same position
events.append((left, -height, 0))
# End event: positive height
events.append((right, height, 1))
# Sort events by position, then by type (start before end)
events.sort()
# Max heap to track current heights
heights = SortedList([0]) # Start with ground level
result = []
prev_max_height = 0
for pos, h, event_type in events:
if event_type == 0:
# Start event, add height
heights.add(-h)
else:
# End event, remove the height
heights.remove(h)
curr_max_height = heights[-1]
# If the max height changed, add a skyline point
if curr_max_height != prev_max_height:
result.append([pos, curr_max_height])
prev_max_height = curr_max_height
return resultO(n log n)O(n)This is not really a 'pure' sweep line problem as we saw above. But the idea of creating these events, sorting them, and iterating over them can be considered 'sweep line' as well.
Key insight: We use a max heap/sorted list to efficiently track the tallest building at each point. The skyline only changes when the maximum height changes, so we only add points at those positions.
We need to prioritize larger heights first in starts, because we could have a higher new start interval and a closing lower height at that exact same x position.