8. Merge Intervals in Java : FAANG Interviews

In many real-world scenarios, we encounter situations where we need to manage a series of time intervals, such as booking appointments, processing ranges of values, or scheduling events. One common problem in this area is the Merge Intervals problem. The challenge is to collect intervals and merge any overlapping ones.

Problem Definition

You are given a collection of intervals. Each interval is represented as a pair of integers [start, end], where start is the beginning of the interval, and end is the end of the interval. Your task is to merge all overlapping intervals.

For example:

Input:

[[1, 3], [2, 4], [5, 7], [6, 8]]

Output:

[[1, 4], [5, 8]]

Approach

To solve the problem efficiently, we can break it down into the following steps:

1. Sorting: Sort the intervals by their start times.
2. Merging: Iterate through the sorted intervals and merge overlapping ones.

Step 1: Sorting Intervals

The first step is to sort the intervals based on their start times. This ensures that we can easily compare each interval with the next one. The overlapping intervals will be adjacent in the sorted list, making identifying and merging them easier.

Step 2: Merging Intervals

Once the intervals are sorted, we can iterate through them and merge the overlapping ones. Specifically, for each interval:

• If it does not overlap with the previous interval, add it to the result.
• If it overlaps with the previous interval, merge the two intervals by updating the end of the previous interval to the maximum of the two intervals' ends.

Time Complexity Optimization

Sorting the intervals takes $O(n \log n)$, where $n$ is the number of intervals. After sorting, the merge operation can be performed in a single pass through the list, taking $O(n)$. Therefore, the overall time complexity of the solution is $O(n \log n)$.

Java Code Implementation

Let's now look at the Java implementation of the solution.

import java.util.*;

public class MergeIntervals {

    public static List<int[]> mergeIntervals(List<int[]> intervals) {
        // Step 1: Sort intervals by start times
        intervals.sort((a, b) -> Integer.compare(a[0], b[0]));

        // List to store merged intervals
        List<int[]> merged = new ArrayList<>();

        // Iterate through sorted intervals
        for (int[] interval : intervals) {
            // If merged is empty or current interval doesn't overlap with the last merged one, add it
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                // Merge the current interval with the last one in the merged list
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
            }
        }

        return merged;
    }

    public static void main(String[] args) {
        // Example input
        List<int[]> intervals = new ArrayList<>();
        intervals.add(new int[]{1, 3});
        intervals.add(new int[]{2, 4});
        intervals.add(new int[]{5, 7});
        intervals.add(new int[]{6, 8});

        // Merging the intervals
        List<int[]> mergedIntervals = mergeIntervals(intervals);

        // Output the merged intervals
        for (int[] interval : mergedIntervals) {
            System.out.println(Arrays.toString(interval));
        }
    }
}

Explanation of the Code

1. Sorting: We use intervals.sort((a, b) -> Integer.compare(a[0], b[0])) to sort the intervals based on their start time. This ensures we can process the intervals in order and efficiently check for overlaps.

2. Merging: We initialize an empty list merged to store the merged intervals. For each interval in the sorted list:

   • If the list is empty or the current interval does not overlap with the last merged interval (i.e., the end of the last merged interval is less than the start of the current interval), we simply add the current interval to the result.
   • If the current interval overlaps with the last merged interval, we update the end of the last merged interval to the maximum of the two intervals' end values.

3. Output: Finally, we print out the merged intervals.

Example Walkthrough

Let's walk through the provided example:

Input:

[[1, 3], [2, 4], [5, 7], [6, 8]]

1. Sorting: The intervals are sorted by their start times:

   [[1, 3], [2, 4], [5, 7], [6, 8]]
   

2. Merging:

   • Start with the first interval [1, 3]. It's added to the merged list.
   • The next interval [2, 4] overlaps with the last merged interval [1, 3], so we merge them into [1, 4].
   • The next interval [5, 7] does not overlap with [1, 4], so we add it to the merged list.
   • The last interval [6, 8] overlaps with [5, 7], so we merge them into [5, 8].

Output:

[[1, 4], [5, 8]]

Time Complexity

• Sorting: $O(n \log n)$
• Merging: $O(n)$ Thus, the total time complexity is $O(n \log n)$, where $n$ is the number of intervals.

Summary

The Merge Intervals problem is an excellent example of how sorting and interval comparison can help efficiently solve overlapping range problems. The solution here leverages sorting and a single pass through the intervals to achieve optimal time complexity. Understanding this approach helps solve this specific problem and builds a foundation for working with other range-based issues in Java.

Please stay tuned; I will update Point 6 of the FANNG Interview series; please check the top 10 interview questions here.