Non Overlapping Intervals Minimum Removal in DSA Python - Build from Scratch

Non Overlapping Intervals Minimum Removal

📖 Scenario: You are organizing a conference with multiple talks scheduled as time intervals. Some talks overlap, and you want to remove the minimum number of talks so that no two talks overlap.

🎯 Goal: Build a program that finds the minimum number of intervals to remove to make the rest non-overlapping.

📋 What You'll Learn

Create a list of intervals with exact values

Add a variable to count removals

Implement logic to find minimum removals for non-overlapping intervals

Print the minimum number of intervals to remove

💡 Why This Matters

🌍 Real World

Scheduling talks, meetings, or tasks without conflicts is common in event planning and project management.

💼 Career

Understanding interval scheduling and greedy algorithms is useful for software engineers working on calendar apps, resource allocation, and optimization problems.

1

Create the list of intervals

Create a list called intervals with these exact intervals: [1, 3], [2, 4], [3, 5], [6, 7], [8, 10], [9, 11]

DSA Python

# Your code here

Hint

Use a list of lists to represent intervals.

2

Add a variable to count removals

Add a variable called removals and set it to 0 to count how many intervals we remove

DSA Python

intervals = [[1, 3], [2, 4], [3, 5], [6, 7], [8, 10], [9, 11]]
# Your code here

Hint

Initialize removals to zero before processing intervals.

3

Implement logic to find minimum removals

Sort intervals by their end time using intervals.sort(key=lambda x: x[1]). Then create a variable prev_end set to the end of the first interval. Use a for loop with variable i from 1 to len(intervals) to check if the start of the current interval is less than prev_end. If yes, increment removals. Otherwise, update prev_end to the current interval's end.

DSA Python

intervals = [[1, 3], [2, 4], [3, 5], [6, 7], [8, 10], [9, 11]]
removals = 0
# Your code here

Hint

Sort intervals by end time to greedily keep intervals that finish earliest.

4

Print the minimum number of intervals to remove

Print the value of removals using print(removals)

DSA Python

intervals = [[1, 3], [2, 4], [3, 5], [6, 7], [8, 10], [9, 11]]
removals = 0
intervals.sort(key=lambda x: x[1])
prev_end = intervals[0][1]
for i in range(1, len(intervals)):
    if intervals[i][0] < prev_end:
        removals += 1
    else:
        prev_end = intervals[i][1]
# Your code here

Hint

The output is the minimum number of intervals to remove to avoid overlaps.