Greedy / Intervals

You are given an array of non-overlapping intervals intervals sorted by start time, and a new interval newInterval. Insert newInterval into intervals so that the result is still sorted and has no overlapping intervals (merge if necessary), and return it.

Because the input is already sorted, no sorting is needed. A single linear pass splits the intervals into three groups:

1. Before: intervals that end before newInterval starts. Add them unchanged.
2. Overlapping: intervals that start on or before newInterval ends. Merge each one into newInterval by taking the minimum start and maximum end.
3. After: all remaining intervals. Add the merged interval, then append them unchanged.

def insert(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
    res = []
    i, n = 0, len(intervals)

    # 1. Intervals completely before newInterval
    while i < n and intervals[i][1] < newInterval[0]:
        res.append(intervals[i])
        i += 1

    # 2. Intervals overlapping newInterval: merge them
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval = [min(newInterval[0], intervals[i][0]),
                       max(newInterval[1], intervals[i][1])]
        i += 1
    res.append(newInterval)

    # 3. Intervals completely after newInterval
    res.extend(intervals[i:])
    return res
    

Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by start time. After sorting, any interval that overlaps the last merged interval must start no later than that interval's end. Walk through the list: if the current interval starts at or before the end of the last merged interval, extend that end with max(end, current_end); otherwise start a new merged interval. Sorting dominates the cost, and the merge pass itself is linear.

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0][:]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged
    

Given an array of intervals where intervals[i] = [start, end], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping. Intervals that only touch at an endpoint (such as [1, 2] and [2, 3]) do not overlap.

This is the classic interval scheduling problem: removing the fewest intervals is the same as keeping the most. The greedy choice is to sort by end time and always keep the interval that finishes earliest, because it leaves the most room for the intervals after it. Scan in order: if the current interval starts at or after the end of the last kept interval, keep it; otherwise it overlaps, so remove it (count it). Sorting by start time and comparing ends also works, but sorting by end makes the greedy argument simple.

def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])
    prev_end = float('-inf')
    removed = 0
    for start, end in intervals:
        if start >= prev_end:
            prev_end = end  # keep this interval
        else:
            removed += 1    # overlaps with the kept one, remove it
    return removed
    

Given an array of meeting time intervals intervals where intervals[i] = [start, end], determine if a person could attend all meetings.

A person can attend all meetings only if no two meetings overlap. Sort the meetings by start time; then it is enough to compare each meeting with the one just before it. If a meeting starts before the previous one ends, there is a conflict. A meeting that starts exactly when the previous one ends is allowed.

def canAttendMeetings(intervals: list[list[int]]) -> bool:
    intervals.sort()
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            return False
    return True
    

Given an array of meeting time intervals intervals where intervals[i] = [start, end], return the minimum number of conference rooms required.

Sort the start times and the end times separately. The identity of each meeting does not matter, only how many are running at once. Process meetings in order of start time with a pointer e on the earliest end time. If the next meeting starts at or after that earliest end, a room has just been freed, so reuse it by moving e forward. Otherwise every room is busy and a new room is needed. The total rooms opened is the answer. This is simpler than the equivalent min-heap solution and uses no heap operations.

def minMeetingRooms(intervals: list[list[int]]) -> int:
    starts = sorted(i[0] for i in intervals)
    ends = sorted(i[1] for i in intervals)

    rooms = 0
    e = 0
    for s in starts:
        if s >= ends[e]:
            e += 1      # a meeting has ended, reuse its room
        else:
            rooms += 1  # all rooms busy, open a new one
    return rooms
    

You are given a 2D integer array intervals, where intervals[i] = [left, right] describes an interval containing all integers from left to right inclusive (its size is right - left + 1), and an integer array queries. For each query q, return the size of the smallest interval that contains q, or -1 if none exists.

Checking every interval for every query is \(O(N \cdot Q)\). Instead, answer the queries offline in increasing order while sweeping through the intervals sorted by start. For each query q:

1. Push every interval with left <= q into a min-heap keyed by (size, right).
2. Pop from the top of the heap while its interval ends before q. Such an interval can never contain q or any larger query, so it is safe to discard permanently.
3. The heap top is now the smallest interval that contains q, or the heap is empty and the answer is -1.

Store results in a dictionary keyed by query value so the answers can be returned in the original query order, including duplicate queries. Each interval is pushed and popped at most once.

import heapq

def minInterval(intervals: list[list[int]], queries: list[int]) -> list[int]:
    intervals.sort()
    heap = []   # (size, right)
    res = {}
    i = 0

    for q in sorted(queries):
        # Add all intervals that start on or before q
        while i < len(intervals) and intervals[i][0] <= q:
            left, right = intervals[i]
            heapq.heappush(heap, (right - left + 1, right))
            i += 1

        # Discard intervals that end before q
        while heap and heap[0][1] < q:
            heapq.heappop(heap)

        res[q] = heap[0][0] if heap else -1

    return [res[q] for q in queries]