Non-Overlapping Intervals (Revisited) 🎯

Welcome back to CodeYourCraft! Today, we're going to dive into a fascinating topic: Non-Overlapping Intervals. This concept is crucial in various real-world applications such as scheduling, resource allocation, and more. Let's get started!

Understanding Intervals 📝

An interval is a contiguous period of time or range of values. In programming, we often deal with intervals as a pair of bounds (start and end).

python

interval = (start, end)

The Problem of Non-Overlapping Intervals 💡

Given a list of intervals, the goal is to find the maximum number of non-overlapping intervals that can be selected.

Let's understand this with an example:

python

intervals = [(1, 3), (6, 9), (2, 5), (7, 8)]

In this case, the non-overlapping intervals are (2, 5) and (7, 8). We can't select (1, 3) and (6, 9) because they overlap with the other intervals.

Solving the Problem ✅

We'll solve this problem using a sorting and merging approach. Here's a step-by-step breakdown:

Sort the intervals based on their start time.
Merge adjacent non-overlapping intervals.
Count the number of merged intervals.

Example Code

python

def non_overlapping_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    result = []
    current = intervals[0]

    for interval in intervals:
        if interval[0] >= current[1]:
            current = interval
        else:
            result.append(current)
            current = interval

    result.append(current)  # Add the last interval

    return len(result)

Let's test this function with our example:

python

intervals = [(1, 3), (6, 9), (2, 5), (7, 8)]
print(non_overlapping_intervals(intervals))  # Output: 2

Real-World Applications 🎯

Non-overlapping intervals are useful in various scenarios, such as:

Scheduling meetings without conflicts
Allocating resources (like servers or database connections) efficiently
Optimizing network traffic routing

Conclusion ✅

We've learned how to find the maximum number of non-overlapping intervals in a given list of intervals. This concept has practical applications in scheduling, resource management, and more.

Keep up the great learning journey, and see you in the next lesson! 🚀