Interval problems: sort by start or end time, then greedily merge, remove, or query. The 'sweep line' technique handles complex interval queries.
Problems: 6
Easy: 1
Medium: 4
Hard: 1
Learning approach: Read the problem. Try the test cases yourself first.
Click Hint if stuck — it guides without spoiling.
Use Show Solution only after a genuine attempt.
Then hit Let's Code to run your solution live.
Three phases: (1) add all intervals that end before new starts, (2) merge all overlapping intervals, (3) add remaining.
Python Solution
def insert(intervals, newInterval):
result = []
i = 0
# Phase 1: intervals that end before newInterval starts
while i < len(intervals) and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
# Phase 2: merge overlapping intervals
while i < len(intervals) and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
result.append(newInterval)
# Phase 3: remaining intervals
result.extend(intervals[i:])
return result
Key idea: Three-phase sweep. Phase 1: copy intervals entirely before the new one. Phase 2: merge all overlapping intervals into newInterval by expanding its bounds. Phase 3: append the rest.
Sort by start time. For each interval, if it overlaps with the last merged interval (start ≤ last end), extend the last interval's end.
Python Solution
def merge(intervals):
intervals.sort()
result = [intervals[0]]
for start, end in intervals[1:]:
if start <= result[-1][1]: # overlapping
result[-1][1] = max(result[-1][1], end)
else:
result.append([start, end])
return result
Key idea: Sort by start. Maintain a result list. For each interval, if it overlaps with the last result interval, extend its end. Otherwise, append as a new interval.
Sort by end time. Greedily keep intervals that don't overlap with the last kept one. Count the rest as removed.
Python Solution
def eraseOverlapIntervals(intervals):
intervals.sort(key=lambda x: x[1]) # sort by end time
count = 0
prev_end = float('-inf')
for start, end in intervals:
if start >= prev_end:
prev_end = end # keep this interval
else:
count += 1 # remove this interval (overlaps with previous)
return count
Key idea: Sorting by end time and greedily keeping non-overlapping intervals is the Activity Selection problem. By always keeping the interval that ends earliest, we maximize the number kept.
Sort by start time. If any meeting starts before the previous one ends, there's a conflict.
Python Solution
def canAttendMeetings(intervals):
intervals.sort()
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i-1][1]:
return False # overlap detected
return True
Key idea: Sort by start. Check if any meeting starts before the previous ends. After sorting, overlaps can only occur between adjacent meetings.
Sort meetings by start. Use a min-heap of room end times. If the earliest-ending room is free, reuse it; otherwise open a new room.
Python Solution
import heapq
def minMeetingRooms(intervals):
if not intervals:
return 0
intervals.sort()
heap = [] # min-heap of end times
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heapreplace(heap, end) # reuse the room that ends earliest
else:
heapq.heappush(heap, end) # need a new room
return len(heap)
Key idea: Min-heap of room end times. For each meeting, if the room that ends soonest is free by the start time, reuse it. Otherwise allocate a new room. Heap size = rooms needed.
Sort queries. Use a min-heap of (size, end) for intervals that include the current query point. Remove expired intervals. The heap top is the answer.
Python Solution
import heapq
def minInterval(intervals, queries):
intervals.sort()
sorted_queries = sorted(enumerate(queries), key=lambda x: x[1])
result = {}
heap = [] # (interval_size, end)
i = 0
for idx, q in sorted_queries:
# Add all intervals that start <= q
while i < len(intervals) and intervals[i][0] <= q:
l, r = intervals[i]
heapq.heappush(heap, (r - l + 1, r))
i += 1
# Remove intervals that have ended (end < q)
while heap and heap[0][1] < q:
heapq.heappop(heap)
result[idx] = heap[0][0] if heap else -1
return [result[i] for i in range(len(queries))]
Key idea: Process queries in sorted order. Maintain a heap of active intervals ordered by size. Prune intervals that no longer contain the query point. The smallest active interval is the answer.