Non Overlapping Intervals in O(n log n) Time Complexity using JavaScript

Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 3
Explanation: [1,2], [2, 3] and [3, 4] are non-overlapping.

Your algorithm should run in O(n log n) time and use O(1) extra space.

Understanding the Problem

The core challenge of this problem is to select the maximum number of non-overlapping intervals from a given collection. This problem is significant in various applications such as scheduling, resource allocation, and event planning where overlapping intervals can cause conflicts.

Potential pitfalls include misunderstanding the definition of non-overlapping intervals and not considering the optimal way to select intervals to maximize the count.

Approach

To solve this problem, we can use a greedy algorithm. The idea is to always select the interval that ends the earliest and does not overlap with the previously selected interval. This approach ensures that we leave as much room as possible for subsequent intervals.

Here is a step-by-step approach:

1. Sort the intervals based on their end times.
2. Initialize a variable to keep track of the end time of the last added interval.
3. Iterate through the sorted intervals and select an interval if its start time is greater than or equal to the end time of the last added interval.

Algorithm

Let's break down the algorithm step-by-step:

1. Sort the intervals by their end times. This can be done using a sorting algorithm which takes O(n log n) time.
2. Initialize a variable end to keep track of the end time of the last added interval and set it to negative infinity initially.
3. Initialize a counter count to keep track of the number of non-overlapping intervals.
4. Iterate through the sorted intervals:
   • If the start time of the current interval is greater than or equal to end, increment the count and update end to the end time of the current interval.

Code Implementation

// Function to find the maximum number of non-overlapping intervals
function maxNonOverlappingIntervals(intervals) {
    // Sort intervals based on their end times
    intervals.sort((a, b) => a[1] - b[1]);

    // Initialize the end time of the last added interval
    let end = -Infinity;
    // Initialize the count of non-overlapping intervals
    let count = 0;

    // Iterate through the sorted intervals
    for (let interval of intervals) {
        // If the start time of the current interval is greater than or equal to the end time of the last added interval
        if (interval[0] >= end) {
            // Increment the count
            count++;
            // Update the end time to the end time of the current interval
            end = interval[1];
        }
    }

    // Return the count of non-overlapping intervals
    return count;
}

// Example usage
const intervals = [[1,2],[2,3],[3,4],[1,3]];
console.log(maxNonOverlappingIntervals(intervals)); // Output: 3

Complexity Analysis

The time complexity of this algorithm is O(n log n) due to the sorting step. The space complexity is O(1) as we are using a constant amount of extra space.

Edge Cases

Potential edge cases include:

• Empty list of intervals: The output should be 0.
• Intervals with the same start and end times: These should be handled correctly by the sorting step.

Example of edge cases:

Input: []
Output: 0

Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 3

Testing

To test the solution comprehensively, consider the following test cases:

• Simple cases with a few intervals.
• Cases with overlapping intervals.
• Edge cases as mentioned above.

Example test cases:

console.log(maxNonOverlappingIntervals([])); // Output: 0
console.log(maxNonOverlappingIntervals([[1,2],[2,3],[3,4],[1,3]])); // Output: 3
console.log(maxNonOverlappingIntervals([[1,2],[1,2],[1,2]])); // Output: 1
console.log(maxNonOverlappingIntervals([[1,2],[2,3]])); // Output: 2

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Understand the problem requirements and constraints thoroughly.
• Think about different approaches and their time complexities.
• Start with a naive solution and then optimize it.
• Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to solve the problem of finding the maximum number of non-overlapping intervals using a greedy algorithm. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for coding interviews.

Additional Resources

For further reading and practice problems, consider the following resources:

• LeetCode: Non-overlapping Intervals
• GeeksforGeeks: Activity Selection Problem
• Coursera: Algorithms Part I