Next Interval (Find Smallest Start ≥ End)

📋

Next Interval (Find Smallest Start ≥ End)

Edge cases:

</>

IDE

def find_next_intervals(intervals: list[list[int]]) -> list[int]:public int[] findNextIntervals(int[][] intervals)vector<int> findNextIntervals(vector<vector<int>>& intervals)function findNextIntervals(intervals)

def find_next_intervals(intervals):
    # Write your solution here
    pass

class Solution {
    public int[] findNextIntervals(int[][] intervals) {
        // Write your solution here
        return new int[intervals.length];
    }
}

#include <vector>
using namespace std;

vector<int> findNextIntervals(vector<vector<int>>& intervals) {
    // Write your solution here
    return vector<int>(intervals.size(), -1);
}

function findNextIntervals(intervals) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [-1, -1, -1]Not finding any next interval due to missing or incorrect comparison of start >= end.✅ Ensure you compare intervals[j][0] >= intervals[i][1] and track minimal start correctly.

Wrong: [2, -1, -1]Greedy approach picks wrong next interval without minimal start check.✅ Use two max heaps to find the minimal start >= end instead of first found.

Wrong: [1]Single interval input returns index instead of -1.✅ Return -1 for single interval input as no next interval exists.

Wrong: [0, 1, 2]Intervals with same start and end incorrectly map to next intervals with higher indices instead of smallest index.✅ Allow intervals to map to themselves if start == end and pick smallest index.

Wrong: Brute force approach causes TLE on large inputs.✅ Implement O(n log n) two heaps approach to pass performance test.

✓

Test Cases

Try handling empty and single interval inputs explicitly before proceeding.

Beware of greedy mistakes; consider using two heaps to find next intervals efficiently.

Optimize your solution to O(n log n) using sorting and heaps to avoid TLE.

t1_01basic

Input[[2,3],[3,4],[5,6]]

Expected[1,2,-1]

⏱ Performance - must finish in 2000ms

For interval [2,3], next interval with start >= 3 is [3,4] at index 1; for [3,4], next interval with start >= 4 is [5,6] at index 2; for [5,6], no next interval exists, so -1.

💡 Consider sorting intervals by their start times to efficiently find next intervals.

💡 Use two heaps to track max start and max end intervals for pairing.

💡 Pop from max end heap and find suitable interval from max start heap with start >= end.

Why it failed: Incorrect output means you likely did not correctly find the smallest start >= end for each interval. Fix by using two max heaps and pairing intervals properly.

✓ Correctly found next intervals using two heaps approach.

t1_02basic

Input[[1,4],[2,3],[3,4]]

Expected[2,-1,-1]

⏱ Performance - must finish in 2000ms

For [1,4], next interval with start >=4 is [3,4] at index 2; for [2,3], no interval starts >=3; for [3,4], no interval starts >=4.

💡 Check intervals with overlapping end and start times carefully.

💡 Ensure you pick the interval with the smallest start time >= current interval's end.

💡 Use heaps to efficiently find the next interval instead of brute force.

Why it failed: Wrong output likely due to not selecting the minimal start interval >= end. Fix by comparing starts properly and using a max start heap.

✓ Correctly identified next intervals for overlapping and adjacent intervals.

t2_01edge

Input[]

Expected[]

⏱ Performance - must finish in 2000ms

Empty input means no intervals, so output is empty list.

💡 Handle empty input by returning empty output immediately.

💡 Check if input length is zero before processing.

💡 Return an empty list if no intervals exist.

Why it failed: Failing here means code does not handle empty input properly. Fix by adding a check for empty intervals and returning [].

✓ Correctly handles empty input with empty output.

t2_02edge

Input[[5,5]]

Expected[-1]

⏱ Performance - must finish in 2000ms

Single interval has no next interval, so output is [-1].

💡 For single interval, no next interval exists.

💡 Return [-1] for single element input.

💡 Check if n == 1 and return [-1] directly.

Why it failed: Failing means code does not handle single interval case correctly. Fix by returning [-1] when input length is 1.

✓ Correctly returns [-1] for single interval input.

t2_03edge

Input[[3,3],[3,3],[3,3]]

Expected[0,0,0]

⏱ Performance - must finish in 2000ms

All intervals have same start and end; next interval for each is itself at index 0 (smallest start >= end).

💡 Intervals with same start and end may map to themselves.

💡 Check if start >= end condition includes equality.

💡 Return the smallest index interval with start >= end, even if it is the same interval.

Why it failed: Failing means code excludes intervals with start == end or does not handle duplicates properly. Fix by allowing start == end and returning smallest index.

✓ Correctly handles intervals with identical start and end.

t2_04edge

Input[[10,20],[5,10],[0,5]]

Expected[-1,0,1]

⏱ Performance - must finish in 2000ms

Intervals sorted in descending order; next interval for [10,20] none, for [5,10] next is [10,20], for [0,5] next is [5,10].

💡 Intervals may be unsorted or descending; do not assume sorted input.

💡 Sort intervals by start before processing.

💡 Use heaps to find next intervals regardless of input order.

Why it failed: Failing means code assumes sorted ascending input. Fix by sorting intervals by start before processing.

✓ Correctly handles descending order intervals.

t3_01corner

Input[[5,7],[1,3],[2,4]]

Expected[-1,2,0]

⏱ Performance - must finish in 2000ms

For [5,7], no interval starts >=7; for [1,3], next interval with start >=3 is [2,4] at index 2; for [2,4], next interval with start >=4 is [5,7] at index 0.

💡 Beware of greedy approach that picks first interval with start >= end without checking minimal start.

💡 Use max heaps to find the minimal start >= end rather than first found.

💡 Pop from max end heap and match with max start heap carefully to avoid greedy trap.

Why it failed: Failing means greedy approach picks wrong next interval. Fix by using two max heaps and pairing intervals properly to find minimal start >= end.

✓ Correctly avoids greedy trap and finds minimal start >= end.

t3_02corner

Input[[1,2],[2,3],[2,3],[3,4]]

Expected[1,3,3,-1]

⏱ Performance - must finish in 2000ms

For [1,2], next interval with start >=2 is [2,3] at index 1; for [2,3] at index 1 and 2, next interval with start >=3 is [3,4] at index 3; for [3,4], no next interval.

💡 Beware of confusing 0/1 knapsack style reuse with this problem's unique interval mapping.

💡 Each interval maps to exactly one next interval or -1; no reuse allowed.

💡 Use heaps to track indices and ensure unique mapping per interval.

Why it failed: Failing means code confuses problem with unbounded reuse or returns wrong indices. Fix by ensuring one-to-one mapping using heaps and indices.

✓ Correctly handles multiple intervals with same start and end.

t3_03corner

Input[[10,20],[20,30],[30,40],[40,50],[50,60]]

Expected[1,2,3,4,-1]

⏱ Performance - must finish in 2000ms

Intervals sorted ascending; each interval's next is the immediate next index except last which has no next.

💡 Check off-by-one errors in indexing next intervals.

💡 Ensure you do not skip intervals or assign -1 prematurely.

💡 Use heaps or binary search to find exact next interval index.

Why it failed: Failing means off-by-one error in next interval index or premature -1 assignment. Fix by careful indexing and comparison.

✓ Correctly handles sorted intervals with sequential next intervals.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

n=100000 intervals at constraint boundary; O(n log n) solution must complete within 2 seconds.

💡 Brute force O(n^2) will time out; use sorting and two heaps for O(n log n).

💡 Use max heaps to efficiently find next intervals without nested loops.

💡 Avoid unnecessary scans; leverage heap properties for pairing.

Why it failed: TLE indicates brute force or inefficient approach. Fix by implementing two heaps approach with O(n log n) complexity.

✓ Efficient O(n log n) solution confirmed by passing performance test.

Practice

1. You are given a list of projects, each with a required minimum capital to start and a profit earned upon completion. You can start with an initial capital and can select up to K projects sequentially, each time only choosing projects you can afford with your current capital. Which algorithmic approach guarantees finding the maximum possible capital after completing up to K projects?

easy

A. Dynamic programming with a 2D table tracking projects and capital states

B. Brute force recursion exploring all project combinations without pruning

C. Simple sorting of projects by profit and picking the top K projects regardless of capital

D. Greedy approach using two heaps: a min-heap for capital requirements and a max-heap for profits

Solution

1. Step 1: Understand problem constraints

   The problem requires selecting projects affordable at each step, maximizing capital after K picks.

2. Step 2: Identify algorithmic pattern

   Using two heaps allows efficient selection: min-heap to filter affordable projects by capital, max-heap to pick the most profitable among them, ensuring optimal capital gain.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two heaps efficiently handle affordability and profit selection [OK]

Hint: Two heaps handle affordability and profit optimally [OK]

Common Mistakes:

• Assuming sorting by profit alone suffices
• Using brute force without pruning
• Confusing DP with this greedy heap approach

2. You need to find the median of every contiguous subarray of size k in an array of integers. Which algorithmic approach guarantees an efficient solution with O(n log k) time complexity?

easy

A. Use a sliding window with sorting each window independently.

B. Apply a greedy algorithm that picks the middle element of each window without sorting.

C. Maintain two balanced heaps (max-heap and min-heap) to track the median dynamically.

D. Use a dynamic programming approach to precompute medians for all subarrays.

Solution

1. Step 1: Understand the problem constraints

   Finding medians for all sliding windows requires efficient insertion, deletion, and median retrieval.

2. Step 2: Evaluate algorithmic approaches

   Sorting each window is expensive (O(n k log k)), DP doesn't apply here, and greedy fails to maintain order. Two heaps maintain balance and allow O(log k) updates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two heaps support efficient median retrieval and updates [OK]

Hint: Two heaps maintain median efficiently in sliding windows [OK]

Common Mistakes:

• Thinking sorting each window is efficient enough
• Assuming greedy can find median without order
• Confusing DP applicability

3. Consider the following buggy code for finding employee free time. Which line contains the subtle bug that causes incorrect free time intervals?

def employeeFreeTime(schedule):
    intervals = [iv for employee in schedule for iv in employee]
    intervals.sort(key=lambda x: x[0])
    free_times = []
    prev_end = intervals[0][1]
    for i in range(1, len(intervals)):
        start, end = intervals[i]
        if start >= prev_end:
            free_times.append([prev_end, start])
        prev_end = max(prev_end, end)
    return free_times

medium

A. Line with intervals.sort(key=lambda x: x[0])

B. Line with prev_end = max(prev_end, end)

C. Line with if start >= prev_end:

D. Line with prev_end = intervals[0][1]

Solution

1. Step 1: Identify condition for free time

   Free time exists only if start > prev_end, not when start == prev_end, because zero-length intervals are invalid.

2. Step 2: Analyze buggy condition

   The condition uses start >= prev_end, which incorrectly adds zero-length intervals when start == prev_end.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Changing >= to > fixes zero-length interval bug [OK]

Hint: Free time intervals must have positive length [OK]

Common Mistakes:

• Using >= instead of > for gap detection
• Not sorting intervals before merging
• Incorrectly updating prev_end

4. The following code attempts to rearrange a string so that the same characters are at least k distance apart. Identify the line containing the subtle bug that can cause invalid output or failure.

medium

A. Line: heapq.heapify(max_heap) # heapify should be replaced with sort

B. Line: if k == 0: return s # should handle k=1 differently

C. Line: queue.append((char, count)) # decrement count missing

D. Line: if front_count < 0: heapq.heappush(max_heap, (front_count, front_char)) # should check for <= 0

Solution

1. Step 1: Identify decrement of count

   The algorithm must decrement the count of the character after using it, i.e., count + 1 since counts are negative.

2. Step 2: Locate missing decrement

   In the buggy line, count is appended without incrementing, so the character count never decreases, causing infinite loops or invalid results.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct decrement is critical to track usage [OK]

Hint: Check if character count is updated after usage [OK]

Common Mistakes:

• Forgetting to decrement count after popping from heap
• Misusing queue length to enforce k-distance
• Incorrect heap operations or conditions

5. If the data stream allows removal of arbitrary elements (not just the median), which modification to the balanced two heaps approach is necessary to maintain efficient median retrieval?

hard

A. Implement lazy removal with a delayed dictionary to mark elements for removal and prune heaps lazily.

B. Use a balanced binary search tree instead of heaps for O(log n) insertions and removals.

C. Keep a sorted list and perform binary search for insertions and removals.

D. Rebuild both heaps from scratch after each removal to maintain order.

Solution

1. Step 1: Understand removal challenges

   Removing arbitrary elements from heaps is not efficient since heaps do not support O(log n) arbitrary removals.

2. Step 2: Evaluate solutions

   Rebuilding heaps each removal is O(n log n), too slow. Balanced BST supports removals but is more complex and median retrieval is not O(1). Sorted list has O(n) insertion/removal. Lazy removal uses a delayed dictionary to mark elements for removal and prunes them lazily during heap operations, maintaining O(log n) amortized complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Lazy removal enables efficient arbitrary removals -> [OK]

Hint: Lazy removal with delayed map enables efficient arbitrary removals [OK]

Common Mistakes:

• Rebuilding heaps after each removal is inefficient
• Assuming heaps support O(log n) arbitrary removals directly
• Switching to balanced BST loses O(1) median retrieval