Insert Interval into Sorted List in DSA Python - Build from Scratch

Insert Interval into Sorted List

📖 Scenario: Imagine you have a calendar with booked time slots represented as intervals. You want to add a new meeting time and keep the calendar sorted and merged so no overlapping meetings exist.

🎯 Goal: Build a program that inserts a new interval into a sorted list of non-overlapping intervals and merges any overlapping intervals.

📋 What You'll Learn

Create a list called intervals with sorted, non-overlapping intervals as lists of two integers.

Create a list called new_interval representing the interval to insert.

Write code to insert new_interval into intervals and merge overlapping intervals.

Print the final list of merged intervals.

💡 Why This Matters

🌍 Real World

Calendars, booking systems, and timeline management often require inserting and merging time intervals to avoid conflicts.

💼 Career

Understanding interval merging is useful for software engineers working on scheduling apps, event planners, and resource allocation tools.

1

Create the initial sorted list of intervals

Create a list called intervals with these exact intervals: [1, 3], [6, 9].

DSA Python

# Your code here

Hint

Use a list of lists to represent intervals.

2

Create the new interval to insert

Create a list called new_interval with the exact values [2, 5].

DSA Python

intervals = [[1, 3], [6, 9]]
# Your code here

Hint

Just assign the list [2, 5] to new_interval.

3

Insert and merge the new interval

Write code to insert new_interval into intervals and merge overlapping intervals. Use a list called merged to store the result. Iterate over intervals + [new_interval] sorted by start time. Merge intervals if they overlap.

DSA Python

intervals = [[1, 3], [6, 9]]
new_interval = [2, 5]
# Your code here

Hint

Sort all intervals including the new one, then merge overlapping ones by comparing the end of the last merged interval with the start of the current.

4

Print the merged intervals

Print the list merged to show the final merged intervals after insertion.

DSA Python

intervals = [[1, 3], [6, 9]]
new_interval = [2, 5]
merged = []
for interval in sorted(intervals + [new_interval], key=lambda x: x[0]):
    if not merged or merged[-1][1] < interval[0]:
        merged.append(interval)
    else:
        merged[-1][1] = max(merged[-1][1], interval[1])
# Your code here

Hint

Use print(merged) to display the final intervals.