Non Overlapping Intervals in Java (O(n log n) Time Complexity)

Given a collection of intervals, find the maximum number of non-overlapping intervals you can select.

Example 1:

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

Note:

You may assume the interval's end point is always bigger than its start point.
Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.

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. A common pitfall is to assume that intervals with touching borders overlap, but they do not.

Approach

To solve this problem, we can use a greedy algorithm. The idea is to always pick 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.

Naive Solution

A naive solution would involve checking all possible combinations of intervals to find the maximum set of non-overlapping intervals. However, this approach is not optimal and has exponential time complexity.

Optimized Solution

The optimized solution involves the following steps:

Sort the intervals based on their end times.
Iterate through the sorted intervals and select the interval if it does not overlap with the previously selected interval.

This approach ensures that we can find the maximum number of non-overlapping intervals in O(n log n) time complexity due to the sorting step.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Sort the intervals based on their end times.
Initialize a variable to keep track of the end time of the last selected interval.
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 selected interval.
Update the end time of the last selected interval to the end time of the current interval.
Count the number of selected intervals.

Code Implementation

import java.util.Arrays;

public class NonOverlappingIntervals {
    public int maxNonOverlappingIntervals(int[][] intervals) {
        // Sort intervals based on their end times
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        
        int count = 0;
        int end = Integer.MIN_VALUE;
        
        for (int[] interval : intervals) {
            // If the start time of the current interval is greater than or equal to the end time of the last selected interval
            if (interval[0] >= end) {
                count++;
                end = interval[1]; // Update the end time to the end time of the current interval
            }
        }
        
        return count;
    }

    public static void main(String[] args) {
        NonOverlappingIntervals solution = new NonOverlappingIntervals();
        int[][] intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
        System.out.println(solution.maxNonOverlappingIntervals(intervals)); // Output: 3
    }
}

Complexity Analysis

The time complexity of the optimized solution 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.

To test these edge cases, we can add additional test cases in the main method.

Testing

To test the solution comprehensively, we can use a variety of test cases:

Simple cases with a few intervals.
Complex cases with many intervals and overlapping intervals.
Edge cases as mentioned above.

Thinking and Problem-Solving Tips

When approaching such problems, it is essential to:

Understand the problem requirements and constraints thoroughly.
Think about different approaches and their time and space 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, consider the following resources: