Merging Overlapping Intervals

1. Understanding the "Merge Intervals" Problem

The problem is straightforward: you are given a collection of intervals, where each interval is represented by a start and an end point. Your task is to merge all the intervals that overlap and return a new list of non-overlapping intervals that cover all the original ranges.

For example, given [[1,3], [2,6], [8,10], [15,18]]:

• [1,3] and [2,6] overlap. They merge to become [1,6].
• The other intervals, [8,10] and [15,18], do not overlap with [1,6] or each other.
• The final result is [[1,6], [8,10], [15,18]].

An important edge case to consider is when intervals touch at their boundaries, for example, [1,4] and [4,5]. These are also considered overlapping and should be merged into [1,5].

2. The Core Strategy: Sort and Scan

If you try to merge intervals in their given, arbitrary order, the logic can become very complex. You might have to compare every interval with every other interval, leading to an inefficient O(n²) solution.

However, just like in our previous lesson, sorting simplifies everything. If we sort the intervals based on their start times, any potentially overlapping intervals will be adjacent in the sorted list. This allows us to process them in a single, linear scan.

To build a strong intuition for this, let's watch a short video that visualizes the power of sorting.

3. The Merging Algorithm

After sorting, the greedy algorithm is elegant and simple:

1. Sort the intervals based on their start times.
2. Create a merged list and initialize it with the first interval from the sorted list.
3. Iterate through the rest of the sorted intervals, from the second one onwards.
4. For each current interval, look at the last interval in your merged list.
5. Check for overlap: If the current interval's start is less than or equal to the last interval's end (current.start <= last.end), they overlap.
   • Merge: Update the last interval's end to be the maximum of the two end points: last.end = max(last.end, current.end). This extends the merged interval to cover both.
6. No overlap: If they don't overlap, it means the current interval starts a new, non-overlapping block. Simply add it to the merged list.
7. After the loop finishes, the merged list contains the final result.

This visual from w3resource perfectly captures the process:

For a more detailed breakdown of this single-scan approach and its Java implementation, the following article is an excellent guide.

4. A Complete Java Implementation

Since your focus is on practical implementation for interviews, let's analyze a complete, runnable Java solution. This will help solidify your understanding of how to use Arrays.sort with a custom comparator and how to manage the results in an ArrayList.

The key line in the Java implementation is the sort:
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

This uses a lambda expression to define a comparator on the fly, sorting the 2D array intervals based on the first element ([0]) of each inner array. This is a common and concise pattern in modern Java that you should be very comfortable with.

5. Common Variations and Interview Follow-ups

In an interview, after you solve the main problem, you'll often be asked about variations. Here are two very common ones:

a) Non-overlapping Intervals (LeetCode 435)

• Problem: Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
• Connection: This is the inverse of a problem you've already solved: the Activity Selection Problem! The greedy approach here is to find the maximum number of non-overlapping intervals you can keep. The minimum number to remove is simply total intervals - max non-overlapping intervals.
• Greedy Strategy: To find the maximum set of non-overlapping intervals, you sort by end time, not start time. This is a crucial distinction.

b) Meeting Rooms II (LeetCode 253)

• Problem: Given an array of meeting time intervals, find the minimum number of conference rooms required.
• Insight: This is equivalent to finding the maximum number of intervals that are overlapping at any single point in time. This requires a slightly different but related technique, often involving sorting start and end times in separate arrays and using a two-pointer approach, or using a min-heap to track meeting end times. I encourage you to explore this problem on your own as excellent practice.

Conclusion

Congratulations on completing the final lesson! Today, you mastered the "Merge Intervals" problem, a cornerstone of algorithm interviews.

Key Takeaways:

• The most effective strategy for interval problems is almost always to sort the intervals first. For merging, sorting by start time is key.
• The greedy merging algorithm involves a single linear scan after sorting, giving it a time complexity of O(n log n) (dominated by the sort) and a space complexity of O(n) for the result (or O(1) if sorting is in-place and results can be stored in the input array).
• Be aware of common variations, such as finding the minimum removals (Activity Selection pattern, sort by end time) or finding maximum overlaps (Meeting Rooms pattern).

This lesson marks the end of our structured curriculum. You have systematically rebuilt your foundation in Data Structures and Algorithms, from basic collections to advanced topics like Dynamic Programming and Greedy algorithms. The key now is consistent practice. Use the skills you've developed to solve problems on platforms like LeetCode and HackerRank. The "Suggested coding questions to practice" in the EnjoyAlgorithms article is a great place to start.

Best of luck in your technical interviews and competitive programming journey! You have built a strong foundation for success.