Non Overlapping Intervals Minimum Removal in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of minimum removals for overlapping intervals

What is the output of the following code that calculates the minimum number of intervals to remove to avoid overlaps?

DSA Python

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda x: x[1])
    count = 0
    end = float('-inf')
    for interval in intervals:
        if interval[0] >= end:
            end = interval[1]
        else:
            count += 1
    return count

intervals = [[1,3],[2,4],[3,5],[7,8]]
print(eraseOverlapIntervals(intervals))

A 3

B 2

C 1

D 0

💡 Hint

Sort intervals by their end time and count how many overlap.

The code sorts intervals by their end time. It then iterates and counts intervals that overlap with the last chosen interval. Here, only one interval needs removal to avoid overlap.

❓ Predict Output

intermediate

Result of minimum removals with nested intervals

What does the function return for this set of intervals?

DSA Python

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda x: x[1])
    count = 0
    end = float('-inf')
    for interval in intervals:
        if interval[0] >= end:
            end = interval[1]
        else:
            count += 1
    return count

intervals = [[1,10],[2,3],[3,4],[4,5]]
print(eraseOverlapIntervals(intervals))

A 0

B 3

C 2

D 1

💡 Hint

Check how many intervals overlap with the earliest finishing intervals.

After sorting by end time to [[2,3],[3,4],[4,5],[1,10]], the code keeps [2,3], [3,4], [4,5] (non-overlapping as start >= previous end), skips [1,10], removes 1 interval.

🔧 Debug

advanced

Identify the error in interval removal code

What error will this code produce when run?

DSA Python

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda x: x[0])
    count = 0
    end = float('-inf')
    for interval in intervals:
        if interval[0] >= end:
            end = interval[1]
        else:
            count += 1
    return count

intervals = [[1,2],[2,3],[1,3]]
print(eraseOverlapIntervals(intervals))

A Outputs 1

B Raises an error

C Outputs 0

D Outputs 2

💡 Hint

Check if sorting by start time affects overlap counting.

The code sorts by start time instead of end time, but still counts overlaps correctly. It outputs 1 because one interval overlaps.

🧠 Conceptual

advanced

Why sort intervals by end time in minimum removal problem?

Why is sorting intervals by their end time the best approach for minimizing removals to avoid overlaps?

A It sorts intervals randomly to check all possibilities.

B It allows choosing intervals that finish earliest, maximizing non-overlapping intervals.

C It sorts intervals by length to remove the longest intervals first.

D It groups intervals by their start time to remove earliest starting intervals.

💡 Hint

Think about how earliest finishing intervals help fit more intervals without overlap.

Sorting by end time helps pick intervals that free up space earliest, allowing more intervals to fit without overlap, minimizing removals.

❓ Predict Output

expert

Output of minimum removals for complex overlapping intervals

What is the output of the code for this complex set of intervals?

DSA Python

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda x: x[1])
    count = 0
    end = float('-inf')
    for interval in intervals:
        if interval[0] >= end:
            end = interval[1]
        else:
            count += 1
    return count

intervals = [[0,30],[5,10],[15,20],[25,35],[27,40],[40,50]]
print(eraseOverlapIntervals(intervals))

A 2

B 4

C 3

D 1

💡 Hint

Sort by end time and count overlaps carefully.

After sorting by end time to [[5,10],[15,20],[0,30],[25,35],[27,40],[40,50]], keeps [5,10], [15,20], [25,35], [40,50]; removes [0,30] and [27,40], totaling 2 removals.