Non-overlapping Intervals (Max Non-Overlap)

🎯

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.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Greedy Selection by End Time	O(n log n)	O(1)	No	Yes	Code this approach
3. Greedy with Removal Count	O(n log n)	O(1)	No	Yes	Alternative 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. Consider the following Python code that merges intervals in-place after sorting. Given the input intervals = [[1,4],[2,5],[7,9]], what is the returned list after the function completes?

easy

A. [[1,5],[7,9]]

B. [[1,4],[2,5],[7,9]]

C. [[1,5],[2,5],[7,9]]

D. [[1,4],[7,9]]

Solution

1. Step 1: Sort intervals by start time.

   Input is already sorted: [[1,4],[2,5],[7,9]].

2. Step 2: Merge intervals in one pass.

   Compare [2,5] with [1,4]: overlap since 2 <= 4, merge to [1,5]. Then compare [7,9] with [1,5]: no overlap, move index forward and assign [7,9]. Final intervals: [[1,5],[7,9]].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overlapping intervals merged correctly, non-overlapping preserved. [OK]

Hint: Check if current start ≤ last merged end to merge [OK]

Common Mistakes:

• Returning original intervals without merging
• Off-by-one slicing errors

2. Examine the following buggy code for Employee Free Time. Which line contains the subtle bug causing incorrect free time intervals?

medium

A. Line appending end event with (interval[1], -1)

B. Line appending start event with (interval[0], 1)

C. Line updating prev = time inside loop

D. Line sorting events with key=lambda x: (x[0], -x[1])

Solution

1. Step 1: Understand sorting order impact

   End events must come before start events at same time to avoid false free intervals.

2. Step 2: Identify bug in sorting key

   Sorting with key (x[0], -x[1]) puts start events before end events at ties, causing incorrect free time detection.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct sorting is (x[0], x[1]) to put end events before start [OK]

Hint: End events must sort before start events at same time [OK]

Common Mistakes:

• Sorting start before end events at same timestamp

3. Consider the following buggy code for inserting an interval. Which line contains the subtle bug that can cause incorrect output when the input list is empty?

from typing import List

def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    intervals.append(newInterval)
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for i in range(1, len(intervals)):
        if intervals[i][0] <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], intervals[i][1])
        else:
            merged.append(intervals[i])
    return merged

medium

A. Line 5: merged = [intervals[0]]

B. Line 3: intervals.append(newInterval)

C. Line 7: if intervals[i][0] <= merged[-1][1]:

D. Line 9: merged.append(intervals[i])

Solution

1. Step 1: Consider empty intervals input

   If intervals is empty, after appending newInterval, intervals has length 1.

2. Step 2: Check initialization of merged

   Line 5 accesses intervals[0] without checking if intervals is empty before append, which is safe here but if input was empty, intervals[0] is newInterval, so no crash.

3. Step 3: Identify subtle bug

   Actually, no crash here, but if input intervals was empty, sorting and merging still works. The subtle bug is that if intervals was empty and newInterval is appended, the code works, but if the initial intervals list is empty and the code did not append newInterval first, line 5 would crash. So the bug is that the code assumes intervals is non-empty before append, which is not always true.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Accessing intervals[0] without empty check is risky [OK]

Hint: Accessing intervals[0] without empty check causes bug [OK]

Common Mistakes:

• Not handling empty input intervals list
• Assuming intervals always non-empty before append
• Incorrect merging when intervals just touch

4. Suppose the meeting intervals can be reused multiple times (i.e., a meeting can be attended multiple times if no overlaps occur). Which modification to the algorithm is necessary to correctly determine if a person can attend all meetings without overlap?

hard

A. Sort intervals by end time and greedily select intervals to maximize non-overlapping meetings.

B. No change needed; the original algorithm already handles reuse correctly.

C. Use a frequency map to count how many times each interval appears and check overlaps accordingly.

D. Sort intervals by start time and check overlaps as before, but also track counts of repeated intervals.

Solution

1. Step 1: Understand reuse scenario

   Reusing intervals means attending multiple instances of the same meeting, so we want to maximize the number of non-overlapping meetings.

2. Step 2: Identify correct approach

   Sorting by end time and greedily selecting earliest finishing meetings maximizes non-overlapping intervals, handling reuse correctly.

3. Step 3: Why other options fail

   Original algorithm only checks if all intervals can be attended once; frequency maps or tracking counts do not solve scheduling conflicts optimally.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Greedy by end time is classic interval scheduling for maximum non-overlapping intervals [OK]

Hint: Reuse requires interval scheduling by end time [OK]

Common Mistakes:

• Assuming original overlap check suffices for reuse
• Trying to track counts without scheduling logic

5. Suppose meetings can be scheduled with negative start or end times (e.g., representing times before a reference point). Which modification to the min-heap approach is necessary to correctly compute the minimum number of meeting rooms?

hard

A. Adjust the comparison in the heap to handle negative end times by using a max-heap instead of min-heap.

B. Sort intervals by absolute value of start times to handle negative values correctly.

C. Sort intervals normally by start time and use the min-heap approach as usual; negative times do not affect logic.

D. No modification needed; the existing min-heap approach works regardless of negative times.

Solution

1. Step 1: Understand sorting by start time works with negative values.

   Sorting by start time orders intervals correctly even if times are negative.

2. Step 2: Confirm min-heap logic remains valid.

   Heap tracks earliest end time; negative values do not affect min-heap property or comparison logic.

3. Step 3: No need for absolute value sorting or max-heap.

   Using absolute values or max-heap breaks the logic of interval ordering and room reuse.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Negative times do not change sorting or heap logic [OK]

Hint: Sorting by start time works even with negative times [OK]

Common Mistakes:

• Sorting by absolute values breaks interval order
• Switching to max-heap unnecessarily
• Assuming negative times require special handling