NeetCode 150 · Intervals

Intervals Problems

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.
01 Medium Array
Given sorted non-overlapping intervals and a new interval, insert and merge if necessary. Return the resulting intervals.
Test Cases
insert([[1,3],[6,9]], [2,5]) → [[1,5],[6,9]] insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]) → [[1,2],[3,10],[12,16]]
3-phase: before/overlap/afterO(n)
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.
Time: O(n).
Space: O(n).
02 Medium ArraySorting
Given array of intervals, merge all overlapping intervals and return the non-overlapping result.
Test Cases
merge([[1,3],[2,6],[8,10],[15,18]]) → [[1,6],[8,10],[15,18]] merge([[1,4],[4,5]]) → [[1,5]]
sort by startextend end if overlapO(n log n)
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.
Time: O(n log n).
Space: O(n).
03 Medium ArrayGreedySortingDP
Find the minimum number of intervals to remove to make the rest non-overlapping.
Test Cases
eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]]) → 1 eraseOverlapIntervals([[1,2],[1,2],[1,2]]) → 2
sort by endgreedy keep non-overlapO(n log n)
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.
Time: O(n log n).
Space: O(1).
04 Easy ArraySorting
Given list of meeting time intervals, determine if a person can attend all meetings (no overlap).
Test Cases
canAttendMeetings([[0,30],[5,10],[15,20]]) → False canAttendMeetings([[7,10],[2,4]]) → True
sort by startcheck adjacent overlapO(n log n)
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.
Time: O(n log n).
Space: O(1).
05 Medium ArrayGreedySortingHeap
Return the minimum number of conference rooms required for all meetings.
Test Cases
minMeetingRooms([[0,30],[5,10],[15,20]]) → 2 minMeetingRooms([[2,7]]) → 1
min heap of end timessort by startO(n log n)
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.
Time: O(n log n).
Space: O(n).
06 Hard ArrayBinary SearchSortingHeap
For each query point, find the size of the smallest interval that contains it. Return results in original query order.
Test Cases
minInterval([[1,4],[2,4],[3,6],[4,4]],[2,3,4,5]) → [3,3,1,4] minInterval([[2,3],[2,5],[1,8],[20,25]],[2,19,22,6]) → [2,-1,4,-1]
sort queriessweep + min heapO((n+q) log n)
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.
Time: O((n+q) log n).
Space: O(n+q).
← Prev Category Next Category →