Next Interval (Find Smallest Start ≥ End)

▶

Steps

setup

Initialize result array and heaps

We initialize the result array with -1 for all intervals and create empty max-heaps for start and end times.

💡 Setting up these data structures is essential to store intermediate results and efficiently access intervals by start and end times.

Line:

result = [-1] * n
max_start_heap = []
max_end_heap = []

💡 The result array is ready to store answers; heaps are empty but ready to be filled.

setup

Push intervals into max_start_heap

We push each interval's start time (negated) and index into max_start_heap to build a max-heap by start time.

💡 Using negative start times allows Python's min-heap to behave like a max-heap, so the interval with the largest start is at the root.

Line:

for i, (start, end) in enumerate(intervals):
    heapq.heappush(max_start_heap, (-start, i))

💡 max_start_heap now contains all intervals keyed by start time for quick access to largest start.

setup

Push intervals into max_end_heap

We push each interval's end time (negated) and index into max_end_heap to build a max-heap by end time.

💡 This heap allows us to process intervals in order of decreasing end times, starting with the interval that ends last.

Line:

for i, (start, end) in enumerate(intervals):
    heapq.heappush(max_end_heap, (-end, i))

💡 max_end_heap now contains all intervals keyed by end time for quick access to largest end.

delete

Pop interval with max end from max_end_heap

We pop the interval with the largest end time from max_end_heap to find the next interval for it.

💡 Processing intervals in descending order of end time ensures we find the next interval for the latest finishing intervals first.

Line:

end, end_idx = heapq.heappop(max_end_heap)
end = -end

💡 The interval [5,6] with index 2 is selected for finding its next interval.

compare

Check if any start ≥ end exists for popped interval

We check if the max start in max_start_heap is at least the popped interval's end time (6).

💡 If no interval starts at or after 6, the next interval is -1 for this interval.

Line:

if not max_start_heap or -max_start_heap[0][0] < end:
    continue

💡 No interval starts at or after 6, so result[2] remains -1.

delete

Pop interval with max end from max_end_heap

Pop the next interval with the largest end time, which is [3,4] at index 1.

💡 We now find the next interval for [3,4].

Line:

end, end_idx = heapq.heappop(max_end_heap)
end = -end

💡 Interval [3,4] is selected for next interval search.

compare

Check if any start ≥ end exists for popped interval

Check if max start in max_start_heap is at least 4 (end of popped interval).

💡 We want to find intervals starting at or after 4.

Line:

if not max_start_heap or -max_start_heap[0][0] < end:
    continue

💡 There are candidates for next interval for [3,4].

delete

Pop candidates with start ≥ end

Pop intervals from max_start_heap with start ≥ 4 and collect candidates.

💡 We gather all intervals that could be the next interval for [3,4].

Line:

while max_start_heap and -max_start_heap[0][0] >= end:
    start, start_idx = heapq.heappop(max_start_heap)
    candidates.append((start, start_idx))

💡 Candidate intervals are [5,6] (index 2).

compare

Select candidate with smallest start

Select the candidate with the smallest start time (largest negative start) among candidates.

💡 Choosing the smallest start ≥ end ensures the next interval is the earliest possible.

Line:

best = max(candidates, key=lambda x: x[0])

💡 The next interval for [3,4] is [5,6] at index 2.

insert

Assign next interval index and push back other candidates

Assign the best candidate's index to result for the popped interval and push back other candidates to max_start_heap.

💡 This step finalizes the next interval for [3,4] and restores the heap for further processing.

Line:

result[end_idx] = best[1]
for c in candidates:
    if c != best:
        heapq.heappush(max_start_heap, c)

💡 Result array updated: result[1] = 2; heap restored with remaining candidates.

delete

Pop interval with max end from max_end_heap

Pop the last interval with max end, which is [2,3] at index 0.

💡 We now find the next interval for [2,3].

Line:

end, end_idx = heapq.heappop(max_end_heap)
end = -end

💡 Interval [2,3] is selected for next interval search.

compare

Check if any start ≥ end exists for popped interval

Check if max start in max_start_heap is at least 3 (end of popped interval).

💡 We want to find intervals starting at or after 3.

Line:

if not max_start_heap or -max_start_heap[0][0] < end:
    continue

💡 There are candidates for next interval for [2,3].

delete

Pop candidates with start ≥ end

Pop intervals from max_start_heap with start ≥ 3 and collect candidates.

💡 We gather all intervals that could be the next interval for [2,3].

Line:

while max_start_heap and -max_start_heap[0][0] >= end:
    start, start_idx = heapq.heappop(max_start_heap)
    candidates.append((start, start_idx))

💡 Candidate intervals are [3,4] (index 1) and [5,6] (index 2).

compare

Select candidate with smallest start

Select the candidate with the smallest start time (largest negative start) among candidates.

💡 Choosing the smallest start ≥ end ensures the next interval is the earliest possible.

Line:

best = max(candidates, key=lambda x: x[0])

💡 The next interval for [2,3] is [3,4] at index 1.

insert

Assign next interval index and push back other candidates

Assign the best candidate's index to result for the popped interval and push back other candidates to max_start_heap.

💡 This step finalizes the next interval for [2,3] and restores the heap for further processing.

Line:

result[end_idx] = best[1]
for c in candidates:
    if c != best:
        heapq.heappush(max_start_heap, c)

💡 Result array updated: result[0] = 1; heap restored with remaining candidate (-5, 2).

reconstruct

All intervals processed, return result

All intervals have been processed; the result array now contains the indices of the next intervals or -1.

💡 Returning the result completes the algorithm.

Line:

return result

💡 Final result is [1, 2, -1], matching expected output.

import heapq

def find_next_intervals(intervals):
    n = len(intervals)
    result = [-1] * n  # STEP 1
    max_start_heap = []  # STEP 1
    max_end_heap = []  # STEP 1

    for i, (start, end) in enumerate(intervals):  # STEP 2 & 3
        heapq.heappush(max_start_heap, (-start, i))  # STEP 2
        heapq.heappush(max_end_heap, (-end, i))  # STEP 3

    while max_end_heap:  # STEP 4
        end, end_idx = heapq.heappop(max_end_heap)  # STEP 4
        end = -end  # STEP 4

        if not max_start_heap or -max_start_heap[0][0] < end:  # STEP 5,7,12
            continue  # STEP 5,7,12

        candidates = []  # STEP 8,13
        while max_start_heap and -max_start_heap[0][0] >= end:  # STEP 8,13
            start, start_idx = heapq.heappop(max_start_heap)  # STEP 8,13
            candidates.append((start, start_idx))  # STEP 8,13

        best = max(candidates, key=lambda x: x[0])  # STEP 9,14

        result[end_idx] = best[1]  # STEP 10,15

        for c in candidates:  # STEP 10,15
            if c != best:  # STEP 10,15
                heapq.heappush(max_start_heap, c)  # STEP 10,15

    return result  # STEP 16

if __name__ == '__main__':
    intervals = [[2,3],[3,4],[5,6]]
    print(find_next_intervals(intervals))  # Output: [1, 2, -1]

📊

Next Interval (Find Smallest Start ≥ End) - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how two heaps work together to efficiently find the next interval, which is hard to grasp from code alone.

initializemax-heap

empty heap

insertmax-heap

-5,2

0

-3,1

1

-2,0

2

insertmax-heap

-6,2

0

-4,1

1

-3,0

2

extract_maxmax-heap

-4,1

0

-3,0

1

peekmax-heap

-5,2

0

-3,1

1

-2,0

2

extract_maxmax-heap

-5,2

0

-2,0

1

peekmax-heap

-5,2

0

-2,0

1

extract_maxmax-heap

-2,0

0

peekmax-heap

-2,0

0

Added: 2

insertmax-heap

-2,0

0

Added: 2

extract_maxmax-heap

-2,0

0

peekmax-heap

-3,1

0

-2,0

1

extract_maxmax-heap

empty heap

peekmax-heap

empty heap

Added: 1

insertmax-heap

-5,2

0

Added: 1

returnmax-heap

empty heap

Added: [1,2,-1]

Key Takeaways

✓ Using two max-heaps keyed by start and end times allows efficient retrieval of intervals in descending order.

This insight is hard to see from code alone because the heap operations and their purpose are implicit.

✓ Popping intervals from the end heap and matching them with candidates from the start heap finds the next interval with smallest start ≥ end.

Visualizing this matching clarifies why the algorithm finds the correct next interval efficiently.

✓ Pushing back unused candidates maintains heap integrity and ensures no intervals are lost during processing.

This step is subtle and easy to miss in code but critical for correctness.

Practice

1. You are given schedules of multiple employees, each with their working intervals. You want to find all common free time intervals where no employee is working. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Use a greedy approach to pick intervals with earliest end times and find gaps between them.

B. Flatten all intervals from all employees, sort them by start time, then merge overlapping intervals to find gaps.

C. Use dynamic programming to track overlapping intervals and compute free times.

D. Use a min-heap to iteratively merge intervals from each employee's schedule.

Solution

1. Step 1: Understand problem requirements

   The problem requires finding common free intervals across multiple employees, which means merging all intervals to identify gaps.

2. Step 2: Evaluate approaches

   Greedy earliest end time (A) does not guarantee merging all intervals correctly. DP (C) is unnecessary and inefficient here. Min-heap merging (D) is a valid approach but more complex than flattening and sorting. Flattening and sorting all intervals (B) ensures all intervals are processed in order, enabling correct gap detection.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Flattening and sorting all intervals is the canonical approach for interval merging [OK]

Hint: Flatten and sort all intervals to find gaps [OK]

Common Mistakes:

• Assuming greedy earliest end time works for merging intervals
• Confusing DP with interval merging
• Thinking min-heap is always simpler

2. Given the following Python code for computing sliding window medians, what is the output when nums = [1, 3, -1] and k = 3?

easy

A. [1.0]

B. [1.0, 3.0]

C. [1.0, -1.0]

D. [3.0]

Solution

1. Step 1: Initialize window and compute median

   Window = [1, 3, -1] sorted -> [-1, 1, 3], median at index 1 (k//2) is 1.0

2. Step 2: Loop from i=k to len(nums)

   Since len(nums) = 3 and k=3, loop does not run, so only one median computed.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only one window median computed [OK]

Hint: No sliding when window size equals array length [OK]

Common Mistakes:

• Assuming loop runs even when window covers entire array
• Misindexing median for odd k
• Returning multiple medians incorrectly

3. Consider the following buggy code snippet for sliding window median using a balanced sorted list. Which line contains the subtle bug that causes incorrect median results for even-sized windows?

medium

A. Line with 'return float(window[k // 2 - 1] + window[k // 2])'

B. Line with 'bisect.insort_left(window, nums[i])'

C. Line with 'idx = bisect.bisect_left(window, nums[i - k])'

D. Line with 'window = sorted(nums[:k])'

Solution

1. Step 1: Analyze median calculation for even k

   Median for even k is average of two middle elements, so sum must be divided by 2.

2. Step 2: Identify bug

   Line returning sum without division causes median to be twice the correct value.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing division by 2 in even median calculation [OK]

Hint: Even median requires averaging two middle elements [OK]

Common Mistakes:

• Forgetting to divide sum by 2 for even k median
• Incorrect index calculation for median
• Wrong removal or insertion causing imbalance

4. What is the time complexity of the optimal max-heap based algorithm for minimizing deviation in an array of size n with maximum element M?

medium

A. O(n^2)

B. O(n log M)

C. O(n log n)

D. O(n log n * log M)

Solution

1. Step 1: Analyze heap operations per element

   Each element is pushed once initially, O(n log n). Then max elements are halved repeatedly, up to log M times.

2. Step 2: Combine heap operations and halving steps

   Each halving involves a pop and push on heap, each O(log n), repeated up to log M times per element, total O(n log n * log M).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Complexity accounts for heap operations and repeated halving [OK]

Hint: Repeated halving causes extra log M factor multiplied by heap ops [OK]

Common Mistakes:

• Ignoring the log M factor from repeated halving
• Confusing n log n with n log M
• Assuming quadratic complexity due to nested loops

5. What is the time complexity of the optimal greedy algorithm that uses a max heap and a fixed-size queue to rearrange a string of length n with m unique characters and distance constraint k?

medium

A. O(n log m) because each character is pushed and popped from a heap of size up to m

B. O(n * k) because each character is processed with a queue of size k

C. O(n^2) because the algorithm may scan the string multiple times to enforce constraints

D. O(m log n) because the heap operations depend on string length n

Solution

1. Step 1: Identify main operations

   Each character is pushed and popped from a max heap of size up to m (number of unique chars), each heap operation costs O(log m).

2. Step 2: Count total operations

   Since total characters are n, total heap operations are O(n), resulting in O(n log m) time complexity. However, the queue operations to enforce the k-distance constraint can cause up to O(n * k) complexity in the worst case because each character waits in the cooldown queue for k steps.

3. Step 3: Choose the tightest upper bound

   Considering the cooldown queue of size k, the overall complexity is O(n * k).

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Queue operations dominate due to cooldown size k [OK]

Hint: Cooldown queue size k affects complexity [OK]

Common Mistakes:

• Ignoring cooldown queue impact
• Assuming heap operations dominate always
• Mixing up m and n in heap operation costs