Bird
Raised Fist0
Interview PrepintervalsmediumAmazonGoogleFacebookBloomberg

Non-overlapping Intervals (Max Non-Overlap)

Choose your preparation mode4 modes available
🎯
Non-overlapping Intervals (Max Non-Overlap)
mediumINTERVALSAmazonGoogleFacebook

Imagine you are organizing a conference with multiple talks, and you want to schedule as many talks as possible without any overlaps in their time slots.

💡 This problem is about selecting the maximum number of intervals that don't overlap. Beginners often struggle because they try to check all combinations or don't realize sorting by end time is key to an efficient solution.
📋
Problem Statement

Given an array of intervals where intervals[i] = [start_i, end_i], find the maximum number of intervals you can select such that no two intervals overlap. Return the maximum count of such non-overlapping intervals.

1 ≤ n ≤ 10^50 ≤ start_i < end_i ≤ 10^9
💡
Example
Input"[[1,3],[2,4],[3,5]]"
Output2

We can select intervals [1,3] and [3,5] which do not overlap.

  • All intervals overlap completely → output 1
  • Intervals are already non-overlapping → output n
  • Intervals with same start and end times → output 1
  • Single interval input → output 1
⚠️
Common Mistakes
Sorting intervals by start time and greedily picking intervals

May select fewer intervals than optimal, failing test cases

✅ Sort intervals by end time instead to maximize room for others

Not updating the last selected interval's end time correctly

Incorrect overlap checks leading to wrong counts

✅ Always update last_end to the end time of the chosen interval

Using inclusive overlap check (start > last_end instead of start >= last_end)

Misses intervals that start exactly when previous ends, reducing count

✅ Use start >= last_end to allow touching intervals without overlap

Trying to solve with DP or recursion without pruning

Code runs too slow and times out on large inputs

✅ Use greedy approach which is optimal and efficient

🧠
Brute Force (Pure Recursion / Nested Loops / etc.)
💡 Starting with brute force helps understand the problem deeply by exploring all possible subsets of intervals, even though it's inefficient.

Intuition

Try every interval and decide whether to include it or not, ensuring no overlaps with previously chosen intervals.

Algorithm

  1. Sort intervals by start time to have a consistent order.
  2. Use recursion to explore two choices for each interval: include it if it doesn't overlap with the last chosen, or skip it.
  3. Keep track of the end time of the last included interval to check for overlaps.
  4. Return the maximum count obtained from all recursive paths.
💡 This approach is hard because it explores all subsets, which grows exponentially, but it clearly shows the problem's combinatorial nature.
</>
Code
from typing import List

def max_non_overlapping_intervals(intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda x: x[0])
    n = len(intervals)

    def backtrack(index: int, last_end: int) -> int:
        if index == n:
            return 0
        # Skip current interval
        skip = backtrack(index + 1, last_end)
        take = 0
        if intervals[index][0] >= last_end:
            take = 1 + backtrack(index + 1, intervals[index][1])
        return max(skip, take)

    return backtrack(0, float('-inf'))

# Driver code
if __name__ == '__main__':
    intervals = [[1,3],[2,4],[3,5]]
    print(max_non_overlapping_intervals(intervals))  # Output: 2
Line Notes
intervals.sort(key=lambda x: x[0])Sort intervals by start time to process them in order
def backtrack(index: int, last_end: int) -> int:Define recursive function to explore choices at each interval
if index == n:Base case: no more intervals to process
skip = backtrack(index + 1, last_end)Option 1: skip current interval and move forward
if intervals[index][0] >= last_end:Check if current interval can be taken without overlap
take = 1 + backtrack(index + 1, intervals[index][1])Option 2: take current interval and update last_end
return max(skip, take)Choose the better option between taking or skipping
return backtrack(0, float('-inf'))Start recursion with no intervals chosen yet
import java.util.*;

public class Main {
    public static int maxNonOverlappingIntervals(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        return backtrack(intervals, 0, Integer.MIN_VALUE);
    }

    private static int backtrack(int[][] intervals, int index, int lastEnd) {
        if (index == intervals.length) return 0;
        int skip = backtrack(intervals, index + 1, lastEnd);
        int take = 0;
        if (intervals[index][0] >= lastEnd) {
            take = 1 + backtrack(intervals, index + 1, intervals[index][1]);
        }
        return Math.max(skip, take);
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,4},{3,5}};
        System.out.println(maxNonOverlappingIntervals(intervals)); // Output: 2
    }
}
Line Notes
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]))Sort intervals by start time for ordered processing
private static int backtrack(int[][] intervals, int index, int lastEnd)Recursive helper to explore choices at each interval
if (index == intervals.length) return 0;Base case: no intervals left
int skip = backtrack(intervals, index + 1, lastEnd);Option to skip current interval
if (intervals[index][0] >= lastEnd)Check if current interval can be taken without overlap
take = 1 + backtrack(intervals, index + 1, intervals[index][1]);Option to take current interval and update lastEnd
return Math.max(skip, take);Return the better choice
System.out.println(maxNonOverlappingIntervals(intervals));Print result for given input
#include <bits/stdc++.h>
using namespace std;

int backtrack(vector<vector<int>>& intervals, int index, int lastEnd) {
    if (index == (int)intervals.size()) return 0;
    int skip = backtrack(intervals, index + 1, lastEnd);
    int take = 0;
    if (intervals[index][0] >= lastEnd) {
        take = 1 + backtrack(intervals, index + 1, intervals[index][1]);
    }
    return max(skip, take);
}

int maxNonOverlappingIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) { return a[0] < b[0]; });
    return backtrack(intervals, 0, INT_MIN);
}

int main() {
    vector<vector<int>> intervals = {{1,3},{2,4},{3,5}};
    cout << maxNonOverlappingIntervals(intervals) << "\n"; // Output: 2
    return 0;
}
Line Notes
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) { return a[0] < b[0]; });Sort intervals by start time for consistent order
int backtrack(vector<vector<int>>& intervals, int index, int lastEnd)Recursive function to explore choices
if (index == (int)intervals.size()) return 0;Base case: no intervals left
int skip = backtrack(intervals, index + 1, lastEnd);Option to skip current interval
if (intervals[index][0] >= lastEnd)Check if current interval can be taken without overlap
take = 1 + backtrack(intervals, index + 1, intervals[index][1]);Option to take current interval
return max(skip, take);Return the best choice
cout << maxNonOverlappingIntervals(intervals) << "\n";Print the result
function maxNonOverlappingIntervals(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const n = intervals.length;

  function backtrack(index, lastEnd) {
    if (index === n) return 0;
    const skip = backtrack(index + 1, lastEnd);
    let take = 0;
    if (intervals[index][0] >= lastEnd) {
      take = 1 + backtrack(index + 1, intervals[index][1]);
    }
    return Math.max(skip, take);
  }

  return backtrack(0, -Infinity);
}

// Driver code
const intervals = [[1,3],[2,4],[3,5]];
console.log(maxNonOverlappingIntervals(intervals)); // Output: 2
Line Notes
intervals.sort((a, b) => a[0] - b[0]);Sort intervals by start time for ordered processing
function backtrack(index, lastEnd)Recursive helper to explore choices
if (index === n) return 0;Base case: no intervals left
const skip = backtrack(index + 1, lastEnd);Option to skip current interval
if (intervals[index][0] >= lastEnd)Check if current interval can be taken without overlap
take = 1 + backtrack(index + 1, intervals[index][1]);Option to take current interval
return Math.max(skip, take);Return the better choice
console.log(maxNonOverlappingIntervals(intervals));Print result for given input
⏱
Complexity
TimeO(2^n)
SpaceO(n) recursion stack

We explore all subsets of intervals, which is exponential in n. Each interval has two choices: take or skip.

💡 For n=20, this means over a million recursive calls, which is impractical.
Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem's exhaustive nature.

🧠
Sorting + Greedy Selection
💡 This approach uses a classic greedy strategy by sorting intervals by their end times and selecting intervals that start after the last chosen interval ends.

Intuition

By always picking the interval that finishes earliest, we leave maximum room for the remaining intervals, maximizing the count.

Algorithm

  1. Sort intervals by their end times in ascending order.
  2. Initialize a variable to track the end time of the last selected interval (start with negative infinity).
  3. Iterate through the sorted intervals, and for each interval, if its start time is at least the last selected end time, select it and update the last selected end time.
  4. Count how many intervals are selected and return this count.
💡 This algorithm is easier to understand once you realize that choosing the earliest finishing interval leaves the most space for others.
</>
Code
from typing import List

def max_non_overlapping_intervals(intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda x: x[1])
    count = 0
    last_end = float('-inf')
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count

# Driver code
if __name__ == '__main__':
    intervals = [[1,3],[2,4],[3,5]]
    print(max_non_overlapping_intervals(intervals))  # Output: 2
Line Notes
intervals.sort(key=lambda x: x[1])Sort intervals by their end time to pick earliest finishing first
count = 0Initialize count of selected intervals
last_end = float('-inf')Track end time of last selected interval, start very low
for start, end in intervals:Iterate over intervals in sorted order
if start >= last_end:Check if current interval does not overlap with last selected
count += 1Select current interval
last_end = endUpdate last selected end time
import java.util.*;

public class Main {
    public static int maxNonOverlappingIntervals(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
        int count = 0;
        int lastEnd = Integer.MIN_VALUE;
        for (int[] interval : intervals) {
            if (interval[0] >= lastEnd) {
                count++;
                lastEnd = interval[1];
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,4},{3,5}};
        System.out.println(maxNonOverlappingIntervals(intervals)); // Output: 2
    }
}
Line Notes
Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]))Sort intervals by end time ascending
int count = 0;Initialize count of selected intervals
int lastEnd = Integer.MIN_VALUE;Track end time of last selected interval
for (int[] interval : intervals)Iterate over sorted intervals
if (interval[0] >= lastEnd)Check if current interval starts after last selected ends
count++;Select current interval
lastEnd = interval[1];Update last selected end time
#include <bits/stdc++.h>
using namespace std;

int maxNonOverlappingIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) { return a[1] < b[1]; });
    int count = 0;
    int lastEnd = INT_MIN;
    for (auto& interval : intervals) {
        if (interval[0] >= lastEnd) {
            count++;
            lastEnd = interval[1];
        }
    }
    return count;
}

int main() {
    vector<vector<int>> intervals = {{1,3},{2,4},{3,5}};
    cout << maxNonOverlappingIntervals(intervals) << "\n"; // Output: 2
    return 0;
}
Line Notes
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) { return a[1] < b[1]; });Sort intervals by end time ascending
int count = 0;Initialize count of selected intervals
int lastEnd = INT_MIN;Track end time of last selected interval
for (auto& interval : intervals)Iterate over intervals
if (interval[0] >= lastEnd)Check if current interval starts after last selected ends
count++;Select current interval
lastEnd = interval[1];Update last selected end time
function maxNonOverlappingIntervals(intervals) {
  intervals.sort((a, b) => a[1] - b[1]);
  let count = 0;
  let lastEnd = -Infinity;
  for (const [start, end] of intervals) {
    if (start >= lastEnd) {
      count++;
      lastEnd = end;
    }
  }
  return count;
}

// Driver code
const intervals = [[1,3],[2,4],[3,5]];
console.log(maxNonOverlappingIntervals(intervals)); // Output: 2
Line Notes
intervals.sort((a, b) => a[1] - b[1]);Sort intervals by end time ascending
let count = 0;Initialize count of selected intervals
let lastEnd = -Infinity;Track end time of last selected interval
for (const [start, end] of intervals)Iterate over intervals
if (start >= lastEnd)Check if current interval starts after last selected ends
count++;Select current interval
lastEnd = end;Update last selected end time
⏱
Complexity
TimeO(n log n)
SpaceO(1)

Sorting takes O(n log n), and a single pass through intervals is O(n). No extra space besides variables.

💡 For n=100,000, sorting is efficient and the linear scan is very fast.
Interview Verdict: Accepted

This is the optimal and standard solution for this problem, suitable for interviews.

🧠
Greedy with Interval Removal Count (Alternative Formulation)
💡 Instead of counting intervals to keep, count how many intervals must be removed to avoid overlaps, which is equivalent but sometimes easier to reason about.

Intuition

By sorting intervals by start time and greedily removing intervals that overlap with the previous chosen interval, we can find the minimum removals, then subtract from total.

Algorithm

  1. Sort intervals by their start times.
  2. Initialize a removal count and track the end time of the last kept interval.
  3. Iterate through intervals, if current interval overlaps with last kept, increment removal count and keep the interval with smaller end time.
  4. Return total intervals minus removal count as the maximum non-overlapping count.
💡 This approach is a variant of the greedy method but focuses on removals instead of selections.
</>
Code
from typing import List

def max_non_overlapping_intervals(intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda x: x[0])
    removals = 0
    last_end = intervals[0][1]
    for i in range(1, len(intervals)):
        if intervals[i][0] < last_end:
            removals += 1
            last_end = min(last_end, intervals[i][1])
        else:
            last_end = intervals[i][1]
    return len(intervals) - removals

# Driver code
if __name__ == '__main__':
    intervals = [[1,3],[2,4],[3,5]]
    print(max_non_overlapping_intervals(intervals))  # Output: 2
Line Notes
intervals.sort(key=lambda x: x[0])Sort intervals by start time to detect overlaps in order
removals = 0Count how many intervals must be removed
last_end = intervals[0][1]Track end time of last kept interval
for i in range(1, len(intervals))Iterate from second interval onward
if intervals[i][0] < last_endCheck if current interval overlaps with last kept
removals += 1Increment removal count due to overlap
last_end = min(last_end, intervals[i][1])Keep interval with smaller end time to minimize future overlaps
else: last_end = intervals[i][1]No overlap, update last_end to current interval's end
import java.util.*;

public class Main {
    public static int maxNonOverlappingIntervals(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        int removals = 0;
        int lastEnd = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < lastEnd) {
                removals++;
                lastEnd = Math.min(lastEnd, intervals[i][1]);
            } else {
                lastEnd = intervals[i][1];
            }
        }
        return intervals.length - removals;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,4},{3,5}};
        System.out.println(maxNonOverlappingIntervals(intervals)); // Output: 2
    }
}
Line Notes
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]))Sort intervals by start time to detect overlaps
int removals = 0;Count intervals to remove
int lastEnd = intervals[0][1];Track end time of last kept interval
for (int i = 1; i < intervals.length; i++)Iterate from second interval
if (intervals[i][0] < lastEnd)Check for overlap with last kept interval
removals++;Increment removal count
lastEnd = Math.min(lastEnd, intervals[i][1]);Keep interval with smaller end time
else { lastEnd = intervals[i][1]; }No overlap, update lastEnd
#include <bits/stdc++.h>
using namespace std;

int maxNonOverlappingIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) { return a[0] < b[0]; });
    int removals = 0;
    int lastEnd = intervals[0][1];
    for (int i = 1; i < (int)intervals.size(); i++) {
        if (intervals[i][0] < lastEnd) {
            removals++;
            lastEnd = min(lastEnd, intervals[i][1]);
        } else {
            lastEnd = intervals[i][1];
        }
    }
    return (int)intervals.size() - removals;
}

int main() {
    vector<vector<int>> intervals = {{1,3},{2,4},{3,5}};
    cout << maxNonOverlappingIntervals(intervals) << "\n"; // Output: 2
    return 0;
}
Line Notes
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) { return a[0] < b[0]; });Sort intervals by start time
int removals = 0;Count intervals to remove
int lastEnd = intervals[0][1];Track end time of last kept interval
for (int i = 1; i < (int)intervals.size(); i++)Iterate from second interval
if (intervals[i][0] < lastEnd)Check for overlap
removals++;Increment removal count
lastEnd = min(lastEnd, intervals[i][1]);Keep interval with smaller end time
else { lastEnd = intervals[i][1]; }No overlap, update lastEnd
function maxNonOverlappingIntervals(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  let removals = 0;
  let lastEnd = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < lastEnd) {
      removals++;
      lastEnd = Math.min(lastEnd, intervals[i][1]);
    } else {
      lastEnd = intervals[i][1];
    }
  }
  return intervals.length - removals;
}

// Driver code
const intervals = [[1,3],[2,4],[3,5]];
console.log(maxNonOverlappingIntervals(intervals)); // Output: 2
Line Notes
intervals.sort((a, b) => a[0] - b[0]);Sort intervals by start time
let removals = 0;Count intervals to remove
let lastEnd = intervals[0][1];Track end time of last kept interval
for (let i = 1; i < intervals.length; i++)Iterate from second interval
if (intervals[i][0] < lastEnd)Check for overlap
removals++;Increment removal count
lastEnd = Math.min(lastEnd, intervals[i][1]);Keep interval with smaller end time
else { lastEnd = intervals[i][1]; }No overlap, update lastEnd
⏱
Complexity
TimeO(n log n)
SpaceO(1)

Sorting takes O(n log n), and a single pass through intervals is O(n). No extra space besides variables.

💡 This approach is as efficient as the previous greedy method but framed differently.
Interview Verdict: Accepted

This approach is equally optimal and useful when the problem is phrased as minimizing removals.

📊
All Approaches - One-Glance Tradeoffs
💡 In interviews, always implement the greedy approach (Approach 2) as it is optimal and efficient.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(2^n)O(n) recursion stackYes (deep recursion)YesMention only - never code
2. Greedy Selection by End TimeO(n log n)O(1)NoYesCode this approach
3. Greedy with Removal CountO(n log n)O(1)NoYesAlternative to approach 2, useful if problem framed differently
💼
Interview Strategy
💡 Use this guide to understand the problem deeply, practice coding the greedy solution, and prepare to explain why greedy works over brute force.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding of the problem's exhaustive nature.Introduce the greedy approach by sorting intervals by end time and selecting non-overlapping intervals.Write clean code for the greedy solution and test with sample inputs.Discuss time and space complexity and possible follow-ups.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 8min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of interval scheduling, ability to optimize brute force to greedy, and coding accuracy.

Common Follow-ups

  • What if intervals are not sorted? → Sort first, then apply greedy.
  • How to handle intervals with equal end times? → Greedy still works; stable sorting or any order is fine.
💡 These follow-ups check your grasp of sorting importance and tie-breaking in greedy algorithms.
🔍
Pattern Recognition

When to Use

1) Problem involves intervals or time ranges, 2) Need to select maximum non-overlapping subsets, 3) Overlaps are defined by start/end times, 4) Goal is to maximize count or minimize removals.

Signature Phrases

'maximum number of intervals you can attend''remove minimum intervals to make schedule non-overlapping'

NOT This Pattern When

Problems requiring DP for weighted intervals or counting all subsets are different patterns.

Similar Problems

Meeting Rooms II - counts minimum rooms needed, related to interval overlapsMinimum Number of Arrows to Burst Balloons - similar greedy approach on intervalsMaximum Length of Pair Chain - similar greedy selection by end time

Practice

(1/5)
1. Consider the following Python code implementing the optimal approach for maintaining disjoint intervals. After executing addNum(1), addNum(3), and addNum(2) in order, what is the final state of self.intervals?
easy
A. [[1, 1], [3, 3]]
B. [[1, 1], [2, 3]]
C. [[1, 2], [3, 3]]
D. [[1, 3]]

Solution

  1. Step 1: Trace addNum(1)

    Intervals empty, append [1,1]. Intervals = [[1,1]]
  2. Step 2: Trace addNum(3) and addNum(2)

    addNum(3): bisect_left finds i=1, no merges, insert [3,3]. Intervals = [[1,1],[3,3]]. addNum(2): bisect_left finds i=1, left_merge true (1's end +1 == 2), right_merge true (3's start -1 == 2), merge intervals[0] and intervals[1] into [1,3], pop intervals[1]. Intervals = [[1,3]]
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Intervals correctly merged into one [OK]
Hint: Merging occurs when val bridges two intervals [OK]
Common Mistakes:
  • Forgetting to merge both sides
  • Inserting duplicates
  • Off-by-one errors in merging
2. Consider the following Python function for interval intersections:
from typing import List

def intervalIntersection(A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
    i, j = 0, 0
    result = []
    while i < len(A) and j < len(B):
        if A[i][1] < B[j][0]:
            i += 1
        elif B[j][1] < A[i][0]:
            j += 1
        else:
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            result.append([start, end])
            if A[i][1] < B[j][1]:
                i += 1
            else:
                j += 1
    return result

A = [[0,2],[5,10],[13,23],[24,25]]
B = [[1,5],[8,12],[15,24],[25,26]]
print(intervalIntersection(A, B))
What is the final output printed by this code?
easy
A. [[1,2],[5,5],[8,10],[15,23],[24,25],[25,26]]
B. [[1,2],[5,5],[8,10],[15,23],[24,25],[25,25]]
C. [[1,2],[5,5],[8,10],[15,23],[24,24],[25,26]]
D. [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Solution

  1. Step 1: Trace first intersection

    Compare [0,2] and [1,5]: overlap is [1,2], add to result.
  2. Step 2: Advance pointers and find all intersections

    Following pointer moves and overlaps yield [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]].
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Matches manual step-by-step intersection results [OK]
Hint: Trace pointer increments carefully to avoid off-by-one errors [OK]
Common Mistakes:
  • Including intervals beyond intersection
  • Merging adjacent but non-overlapping intervals
  • Off-by-one in pointer increments
3. Consider the following Python code that determines if a person can attend all meetings given a list of intervals. What is the return value when the input is [[7,10],[2,4]]?
from typing import List

def can_attend_meetings(intervals: List[List[int]]) -> bool:
    intervals.sort(key=lambda x: x[0])
    end = float('-inf')
    for interval in intervals:
        if interval[0] < end:
            return False
        end = interval[1]
    return True

print(can_attend_meetings([[7,10],[2,4]]))
easy
A. None
B. False
C. Raises an exception
D. True

Solution

  1. Step 1: Sort intervals by start time

    Input [[7,10],[2,4]] becomes [[2,4],[7,10]].
  2. Step 2: Iterate and check overlaps

    Initialize end = -inf. First interval start=2 > -inf, update end=4. Second interval start=7 > 4, update end=10. No overlaps found, return True.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Intervals sorted and no overlaps detected [OK]
Hint: Sort then check if current start < previous end [OK]
Common Mistakes:
  • Confusing return value due to unsorted intervals
4. What is the time complexity of the optimal approach that inserts a new interval into a list of n intervals and merges overlapping intervals, where the approach is to append the new interval, sort all intervals by start time, then merge in one pass?
medium
A. O(n)
B. O(n^2)
C. O(n log n)
D. O(log n)

Solution

  1. Step 1: Identify sorting cost

    Appending is O(1), but sorting n+1 intervals takes O(n log n) time.
  2. Step 2: Identify merging cost

    Merging intervals in one pass is O(n) since each interval is processed once.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Sorting dominates overall time complexity [OK]
Hint: Sorting dominates time complexity -> O(n log n) [OK]
Common Mistakes:
  • Assuming linear time because merging is O(n)
  • Confusing sorting cost with merging cost
  • Thinking recursion stack adds extra complexity
5. The following code attempts to merge intervals in-place after sorting. Identify the line that contains a subtle bug causing incorrect results on some inputs.
medium
A. Line 3: intervals.sort(key=lambda x: x[0])
B. Line 9: intervals[index][1] = max(intervals[index][1], intervals[i][1])
C. Line 12: return intervals # missing slicing after in-place merge
D. Line 8: if intervals[i][0] <= intervals[index][1]:

Solution

  1. Step 1: Understand the in-place merge modifies intervals up to index.

    After merging, only intervals[:index+1] are valid merged intervals.
  2. Step 2: Identify the bug in the return statement.

    Returning the entire intervals list without slicing includes extra unmerged intervals, causing incorrect output.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Return intervals[:index+1] to exclude leftover intervals. [OK]
Hint: Return sliced intervals after in-place merge [OK]
Common Mistakes:
  • Forgetting to slice after in-place merge
  • Modifying list while iterating without adjusting index
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard