Intervals

Phase 2 7 solutions

Intervals

mindmap
  root((Intervals))
    Merge/Insert
      Merge Intervals LC56
      Insert Interval LC57
    Scheduling Rooms
      Meeting Rooms LC252
      Meeting Rooms II LC253
      Meeting Rooms III LC2402
    Sweep Line
      Non-Overlapping Intervals LC435
    Query-Based
      Minimum Interval to Include Each Query LC1851

Problem List

#	Problem	LC #	Difficulty	Key Technique
1	Insert Interval	57	Medium	Linear scan + merge
2	Merge Intervals	56	Medium	Sort + merge
3	Non-Overlapping Intervals	435	Medium	Greedy scheduling
4	Meeting Rooms	252	Easy	Sort + check overlap
5	Meeting Rooms II	253	Medium	Min-heap
6	Meeting Rooms III	2402	Hard	Two heaps
7	Minimum Interval to Include Each Query	1851	Hard	Sort + heap + offline queries

Interval Problem Decision Tree

flowchart TD
    A[Interval Problem] --> B{What is asked?}
    B --> C["Merge / Insert"]
    B --> D["Count rooms / resources"]
    B --> E[Remove minimum intervals]
    B --> F[Answer queries]

    C --> C1[Sort by start, linear merge]
    C --> C2[Insert Interval #57 — binary search + merge]

    D --> D1[Sort by start, min-heap on end times]
    D1 --> D2[Meeting Rooms II #253]
    D1 --> D3[Meeting Rooms III #2402 — two heaps]

    E --> E1[Sort by end, greedy keep earliest end]
    E1 --> E2[Non-Overlapping Intervals #435]

    F --> F1[Offline: sort queries + sweep with heap]
    F1 --> F2[Min Interval per Query #1851]

Merge Intervals Algorithm Flow

flowchart TD
    A[Sort intervals by start time] --> B[result = first interval]
    B --> C[For each remaining interval]
    C --> D{"current.start <= last.end?"}
    D -- Yes --> E[Merge: last.end = max of last.end and current.end]
    D -- No --> F[Append current to result as new interval]
    E --> G{More intervals?}
    F --> G
    G -- Yes --> C
    G -- No --> H[Return result]

    style A fill:#2d6a4f,color:#fff
    style H fill:#1b4332,color:#fff

Sweep Line / Event-Based Approach

flowchart TD
    A[For each interval, emit start +1 and end -1 events] --> B[Sort all events by time]
    B --> C[active = 0, maxActive = 0]
    C --> D[For each event in order]
    D --> E[active += event.delta]
    E --> F[maxActive = max of maxActive and active]
    F --> G{More events?}
    G -- Yes --> D
    G -- No --> H[Return maxActive]

    style A fill:#2d6a4f,color:#fff
    style H fill:#1b4332,color:#fff

Used for: counting max concurrent meetings (Meeting Rooms II alternative)

Meeting Rooms Heap Approach

flowchart TD
    A[Sort meetings by start time] --> B[min-heap = empty, rooms = 0]
    B --> C[For each meeting start, end]
    C --> D{"heap not empty AND heap.top <= start?"}
    D -- Yes --> E[Pop earliest ending room — reuse it]
    D -- No --> F[No room free — allocate new room]
    E --> G[Push end time to heap]
    F --> G
    G --> H{More meetings?}
    H -- Yes --> C
    H -- No --> I[Return heap size = rooms needed]

    style A fill:#2d6a4f,color:#fff
    style I fill:#1b4332,color:#fff

Interval Overlap Detection Logic

flowchart TD
    A[Two intervals A = a1,a2 and B = b1,b2] --> B{Do they overlap?}
    B --> C["Overlap condition: a1 <= b2 AND b1 <= a2"]
    C --> D{True?}
    D -- Yes --> E[Overlapping — merged = min a1 b1, max a2 b2]
    D -- No --> F[Non-overlapping — keep separate]

    E --> G[Use for: Merge Intervals, Insert Interval]
    F --> H[Use for: Non-Overlapping — count removals]

    style E fill:#2d6a4f,color:#fff
    style F fill:#9b2226,color:#fff

Complexity Summary

Problem	Time	Space
Insert Interval	O(n)	O(n)
Merge Intervals	O(n log n)	O(n)
Non-Overlapping Intervals	O(n log n)	O(1)
Meeting Rooms	O(n log n)	O(1)
Meeting Rooms II	O(n log n)	O(n)
Meeting Rooms III	O(n log n)	O(n)
Min Interval per Query	O((n+q) log n)	O(n+q)

Study Order

Meeting Rooms — basic overlap check
Merge Intervals — core merge pattern
Insert Interval — merge with binary search
Non-Overlapping Intervals — greedy scheduling
Meeting Rooms II — heap for resource counting
Meeting Rooms III — two-heap advanced
Minimum Interval per Query — offline + heap

Intervals

Core Intuition

Interval problems reduce to: sort by start (or end), then decide how to merge, count, or schedule. The key insight is that after sorting, you only need to compare the current interval with the last processed one.

Merge: Sort by start; merge if current.start ≤ last.end
Non-overlapping / scheduling: Sort by end; greedy keep non-overlapping
Meeting rooms (count): Sort starts and ends separately (sweep line) or use a min-heap
Query problems: Offline sort + heap

Decision Flowchart

flowchart TD
    A[Interval Problem] --> B{"What's the goal?"}
    B -->|Combine overlapping intervals| C["Sort by start<br/>Merge Intervals"]
    B -->|Insert into sorted list| D["Binary search + merge<br/>Insert Interval"]
    B -->|Remove min intervals to make non-overlapping| E["Sort by end<br/>greedy keep<br/>Non-Overlapping"]
    B -->|Can one person attend all?| F["Sort by start<br/>check overlap<br/>Meeting Rooms I"]
    B -->|Min rooms needed| G{Method preference?}
    G -->|Sweep line| H["Sort starts and ends<br/>two-pointer<br/>Meeting Rooms II"]
    G -->|Heap| I["Min-heap of end times<br/>Meeting Rooms II/III"]
    B -->|Answer range queries| J["Sort queries + intervals<br/>min-heap<br/>Min Interval Query"]

Problems

Insert Interval — LC 57 | Medium

Learn: Three phases: add all intervals ending before new one, merge overlapping, add remaining
Mistake: Forgetting to handle the case where new interval doesn't overlap anything
Complexity: O(n) time, O(n) space
Edge: Empty intervals list; new interval before all; new interval after all; complete overlap

Merge Intervals — LC 56 | Medium

Learn: Sort by start; if current.start ≤ last.end, extend last.end = max(last.end, current.end)
Mistake: Not taking max of end times (one interval may be fully contained in another)
Complexity: O(n log n) time, O(n) space
Edge: Single interval; all intervals overlap into one; no overlaps at all

Non-Overlapping Intervals — LC 435 | Medium

Learn: Sort by end time; greedily keep intervals with earliest end; count removals
Mistake: Sorting by start instead of end; counting kept instead of removed
Complexity: O(n log n) time, O(1) space
Edge: All overlapping → remove n-1; no overlaps → remove 0

Meeting Rooms — LC 252 | Easy

Learn: Sort by start; check if any interval starts before previous ends
Mistake: Not sorting first
Complexity: O(n log n) time, O(1) space
Edge: Single meeting → true; empty → true

Meeting Rooms II — LC 253 | Medium

Learn: Min-heap of end times; if earliest end ≤ current start, reuse room (pop+push); else add room
Mistake: Sweep line approach: sort starts and ends separately, two pointers, increment rooms when start < end
Complexity: O(n log n) time, O(n) space
Edge: All meetings at same time → n rooms; sequential meetings → 1 room

Meeting Rooms III — LC 2402 | Hard

Learn: Two heaps: available rooms (min-heap by room number), occupied rooms (min-heap by end time); assign to earliest-ending room when none available
Mistake: Not tracking which room number is used (need to count per room); not handling tie-breaking (use lowest room number)
Complexity: O(n log n + m log n) time where m=meetings, O(n) space
Edge: More meetings than rooms; meetings with same start time (process in order)

Minimum Interval to Include Each Query — LC 1851 | Hard

Learn: Sort intervals by size; sort queries with original indices; sweep with min-heap (size, end); remove expired intervals
Mistake: Not sorting queries offline; not removing intervals whose end < query
Complexity: O((n+q) log n) time, O(n+q) space
Edge: Query not covered by any interval → -1; multiple intervals covering same query → smallest size

General Edge Cases

Empty interval list
Single interval
Intervals with same start or end time
Fully contained intervals (one inside another)
Queries outside all interval ranges
Integer overflow when computing interval sizes
Intervals given in unsorted order (always sort first)

#	Problem	LC #	Difficulty	Key Technique
1	Insert Interval	57	Medium	Linear scan + merge
2	Merge Intervals	56	Medium	Sort + merge
3	Non-Overlapping Intervals	435	Medium	Greedy scheduling
4	Meeting Rooms	252	Easy	Sort + check overlap
5	Meeting Rooms II	253	Medium	Min-heap
6	Meeting Rooms III	2402	Hard	Two heaps
7	Minimum Interval to Include Each Query	1851	Hard	Sort + heap + offline queries

Insert Interval ▼ expand

from typing import List


class Solution:
    """
    ## 57. Insert Interval

    Given a list of non-overlapping intervals sorted by start time, insert a new interval
    and merge if necessary. Return the resulting list of non-overlapping intervals.

    ### Example
    ```text
    Input:  intervals = [[1,3],[6,9]], newInterval = [2,5]
    Output: [[1,5],[6,9]]

    Input:  intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
    Output: [[1,2],[3,10],[12,16]]
    ```

    ### Constraints
    - 0 <= intervals.length <= 10^4
    - intervals is sorted in ascending order by start
    - intervals[i].length == newInterval.length == 2
    - 0 <= intervals[i][0] <= intervals[i][1] <= 10^5
    """

    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        # Add all intervals ending before new interval starts
        # Merge all overlapping intervals with the new one
        # Add remaining intervals that start after the merged interval ends
        # O(n) time, O(n) space — linear scan and merge
        result = []
        i, n = 0, len(intervals)
        # Add all intervals that end before newInterval starts
        while i < n and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1
        # Merge all overlapping intervals
        while i < n 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)
        # Add remaining intervals
        result.extend(intervals[i:])
        return result


if __name__ == '__main__':
    s = Solution()
    assert s.insert([[1, 3], [6, 9]], [2, 5]) == [[1, 5], [6, 9]]
    assert s.insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]) == [[1, 2], [3, 10], [12, 16]]
    assert s.insert([], [5, 7]) == [[5, 7]]
    assert s.insert([[1, 5]], [2, 3]) == [[1, 5]]
    print("All tests passed.")

Meeting Rooms ▼ expand

from typing import List


class Solution:
    """
    ## 252. Meeting Rooms

    Given an array of meeting time intervals where intervals[i] = [start_i, end_i],
    return true if a person could attend all meetings (no two meetings overlap).

    ### Example
    ```text
    Input:  intervals = [[0,30],[5,10],[15,20]]
    Output: false

    Input:  intervals = [[7,10],[2,4]]
    Output: true
    ```

    ### Constraints
    - 0 <= intervals.length <= 10^4
    - intervals[i].length == 2
    - 0 <= start_i < end_i <= 10^6
    """

    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        # Sort by start; if any meeting starts before previous ends, conflict
        # O(n log n) time, O(1) space — sort by start and check adjacent overlap
        intervals.sort(key=lambda x: x[0])
        for i in range(1, len(intervals)):
            if intervals[i][0] < intervals[i - 1][1]:
                return False
        return True


if __name__ == '__main__':
    s = Solution()
    assert s.canAttendMeetings([[0, 30], [5, 10], [15, 20]]) == False
    assert s.canAttendMeetings([[7, 10], [2, 4]]) == True
    assert s.canAttendMeetings([]) == True
    assert s.canAttendMeetings([[1, 5], [5, 10]]) == True
    print("All tests passed.")

Meeting Rooms Ii ▼ expand

from typing import List
import heapq


class Solution:
    """
    ## 253. Meeting Rooms II

    Given an array of meeting time intervals, return the minimum number of conference rooms required.

    ### Example
    ```text
    Input:  intervals = [[0,30],[5,10],[15,20]]
    Output: 2

    Input:  intervals = [[7,10],[2,4]]
    Output: 1
    ```

    ### Constraints
    - 1 <= intervals.length <= 10^4
    - 0 <= start_i < end_i <= 10^6
    """

    def minMeetingRooms_heap(self, intervals: List[List[int]]) -> int:
        # O(n log n) time, O(n) space — sort + min heap of end times
        intervals.sort(key=lambda x: x[0])
        heap = []  # min-heap of end times
        for start, end in intervals:
            if heap and heap[0] <= start:
                heapq.heapreplace(heap, end)
            else:
                heapq.heappush(heap, end)
        return len(heap)

    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        # Min-heap of end times: if next meeting starts after earliest end, reuse room
        # Otherwise allocate a new room; heap size = rooms needed
        # O(n log n) time, O(n) space — chronological ordering with start/end events
        starts = sorted(s for s, _ in intervals)
        ends = sorted(e for _, e in intervals)
        rooms = end_ptr = 0
        for start in starts:
            if start < ends[end_ptr]:
                rooms += 1
            else:
                end_ptr += 1
        return rooms


if __name__ == '__main__':
    s = Solution()
    assert s.minMeetingRooms([[0, 30], [5, 10], [15, 20]]) == 2
    assert s.minMeetingRooms([[7, 10], [2, 4]]) == 1
    assert s.minMeetingRooms([[1, 5], [2, 6], [3, 7]]) == 3
    assert s.minMeetingRooms_heap([[0, 30], [5, 10], [15, 20]]) == 2
    print("All tests passed.")

Meeting Rooms Iii ▼ expand

from typing import List
import heapq


class Solution:
    """
    ## 2402. Meeting Rooms III

    You have n rooms numbered 0 to n-1. Meetings are given as [start, end] (half-open).
    Each meeting is assigned to the lowest-numbered available room. If no room is free,
    the meeting is delayed until the earliest room becomes free (duration preserved).
    Return the room that held the most meetings (lowest index on tie).

    ### Example
    ```text
    Input:  n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
    Output: 0

    Input:  n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
    Output: 1
    ```

    ### Constraints
    - 1 <= n <= 100
    - 1 <= meetings.length <= 10^5
    - 0 <= start_i < end_i <= 5 * 10^5
    """

    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        # Two heaps: available rooms (min-heap of room indices) and busy rooms (end_time, room)
        # Free up rooms whose end_time <= current meeting start before assigning
        # If no room available, wait for earliest-ending room; track usage count per room
        # O(m log n) time, O(n) space — two heaps: available rooms and ongoing meetings
        meetings.sort()
        available = list(range(n))          # min-heap of free room indices
        ongoing = []                         # min-heap of (end_time, room_index)
        count = [0] * n

        for start, end in meetings:
            # Free up rooms that have finished
            while ongoing and ongoing[0][0] <= start:
                _, room = heapq.heappop(ongoing)
                heapq.heappush(available, room)

            if available:
                room = heapq.heappop(available)
                heapq.heappush(ongoing, (end, room))
            else:
                # Delay: use the room that finishes earliest
                finish, room = heapq.heappop(ongoing)
                heapq.heappush(ongoing, (finish + (end - start), room))

            count[room] += 1

        return count.index(max(count))


if __name__ == '__main__':
    s = Solution()
    assert s.mostBooked(2, [[0, 10], [1, 5], [2, 7], [3, 4]]) == 0
    assert s.mostBooked(3, [[1, 20], [2, 10], [3, 5], [4, 9], [6, 8]]) == 1
    assert s.mostBooked(1, [[0, 1], [1, 2], [2, 3]]) == 0
    print("All tests passed.")

Merge Intervals ▼ expand

from typing import List


class Solution:
    """
    ## 56. Merge Intervals

    Given an array of intervals, merge all overlapping intervals and return an array
    of the non-overlapping intervals that cover all the intervals in the input.

    ### Example
    ```text
    Input:  intervals = [[1,3],[2,6],[8,10],[15,18]]
    Output: [[1,6],[8,10],[15,18]]

    Input:  intervals = [[1,4],[4,5]]
    Output: [[1,5]]
    ```

    ### Constraints
    - 1 <= intervals.length <= 10^4
    - intervals[i].length == 2
    - 0 <= intervals[i][0] <= intervals[i][1] <= 10^4
    """

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # Sort by start time; merge current with next if they overlap
        # Two intervals overlap if next.start <= current.end
        # O(n log n) time, O(n) space — sort by start then merge
        intervals.sort(key=lambda x: x[0])
        result = [intervals[0]]
        for start, end in intervals[1:]:
            if start <= result[-1][1]:
                result[-1][1] = max(result[-1][1], end)
            else:
                result.append([start, end])
        return result


if __name__ == '__main__':
    s = Solution()
    assert s.merge([[1, 3], [2, 6], [8, 10], [15, 18]]) == [[1, 6], [8, 10], [15, 18]]
    assert s.merge([[1, 4], [4, 5]]) == [[1, 5]]
    assert s.merge([[1, 4], [0, 4]]) == [[0, 4]]
    assert s.merge([[1, 4], [2, 3]]) == [[1, 4]]
    print("All tests passed.")

Minimum Interval To Include Each Query ▼ expand

from typing import List
import heapq


class Solution:
    """
    ## 1851. Minimum Interval to Include Each Query

    You are given a 2D integer array intervals and an integer array queries.
    For each query, find the size (end - start + 1) of the smallest interval containing
    the query point. Return -1 if no such interval exists.

    ### Example
    ```text
    Input:  intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
    Output: [3,3,1,4]
    (query 2: [2,4] size 3; query 3: [2,4] size 3; query 4: [4,4] size 1; query 5: [3,6] size 4)

    Input:  intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
    Output: [2,-1,4,6]
    ```

    ### Constraints
    - 1 <= intervals.length <= 10^5
    - 1 <= queries.length <= 10^5
    - 1 <= intervals[i][0] <= intervals[i][1] <= 10^7
    - 1 <= queries[i] <= 10^7
    """

    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        # Sort intervals by length; sort queries with original indices
        # Sweep queries in order; add intervals that start <= query to a min-heap by size
        # Pop intervals from heap that end < query; top of heap is the answer
        # O((n + q) log n) time, O(n + q) space — sort intervals and queries, sweep with min heap
        intervals.sort()
        sorted_queries = sorted(enumerate(queries), key=lambda x: x[1])
        result = [-1] * len(queries)
        heap = []  # (size, end) — min heap by interval size
        i = 0

        for idx, q in sorted_queries:
            # Push all intervals whose start <= q
            while i < len(intervals) and intervals[i][0] <= q:
                start, end = intervals[i]
                heapq.heappush(heap, (end - start + 1, end))
                i += 1
            # Remove intervals that have ended before q
            while heap and heap[0][1] < q:
                heapq.heappop(heap)
            if heap:
                result[idx] = heap[0][0]

        return result


if __name__ == '__main__':
    s = Solution()
    assert s.minInterval([[1, 4], [2, 4], [3, 6], [4, 4]], [2, 3, 4, 5]) == [3, 3, 1, 4]
    assert s.minInterval([[2, 3], [2, 5], [1, 8], [20, 25]], [2, 19, 5, 22]) == [2, -1, 4, 6]
    print("All tests passed.")

Non Overlapping Intervals ▼ expand

from typing import List


class Solution:
    """
    ## 435. Non-overlapping Intervals

    Given an array of intervals, return the minimum number of intervals you need to remove
    to make the rest of the intervals non-overlapping.

    ### Example
    ```text
    Input:  intervals = [[1,2],[2,3],[3,4],[1,3]]
    Output: 1  (remove [1,3])

    Input:  intervals = [[1,2],[1,2],[1,2]]
    Output: 2

    Input:  intervals = [[1,2],[2,3]]
    Output: 0
    ```

    ### Constraints
    - 1 <= intervals.length <= 10^5
    - intervals[i].length == 2
    - -5 * 10^4 <= intervals[i][0] < intervals[i][1] <= 5 * 10^4
    """

    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        # Sort by end time; greedily keep intervals with earliest end
        # Count intervals that must be removed (overlap with last kept)
        # O(n log n) time, O(1) space — sort by end, greedily keep non-overlapping
        intervals.sort(key=lambda x: x[1])
        removed = 0
        prev_end = float('-inf')
        for start, end in intervals:
            if start >= prev_end:
                prev_end = end
            else:
                removed += 1
        return removed


if __name__ == '__main__':
    s = Solution()
    assert s.eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]]) == 1
    assert s.eraseOverlapIntervals([[1, 2], [1, 2], [1, 2]]) == 2
    assert s.eraseOverlapIntervals([[1, 2], [2, 3]]) == 0
    print("All tests passed.")

Merge Intervals

Sort by start, merge overlapping intervals greedily

Intervals sorted by start. Press "Next Step" to merge.