In the field of interval-based scheduling and optimization, the Merge Intervals problem is a well-known algorithmic problem in mathematics and computer science. The problem's primary objective is to combine overlapping intervals within a given set to create a smaller, non-overlapping set of intervals.

Example 1:

Input: Intervals: [[1,3], [2,6], [8,10], [15,18]]

Output: [[1,6], [8,10], [15,18]]

Explanation: It is possible to combine the intervals [1,3] and [2,6] into [1,6] because they overlap. The non-overlapping interval set that results is [[1,6], [8,10], [15,18]].

Example 2:

Input: Intervals = [[1,4], [4,5]]

Output: [1,5]

Explanation: Since the beginning and ending points of the first and second intervals are the same, they overlap, making the intervals [1,4] and [4,5] similar. As a result, it is possible to combine these intervals into one interval [1, 5].

Using Naive Approach

The naive approach is a method to merge overlapping intervals in a list using nested loops. It involves initializing the list, using an outer loop to check for overlap, merging the overlapping intervals, removing the merged interval, updating the merged flag, repeating the process, and returning the merged list. This method is straightforward but less efficient for larger datasets due to the nested loops and the need to compare each interval with every other in the list.

Here's the implementation to merge intervals using a naive approach:

FileName:MergeIntervals.java

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

public class MergeIntervals {

   public static int[][] mergeIntervals(int[][] intervals) {

     if (intervals == null || intervals.length <= 1) {

       return intervals;

     }

     // Sort intervals based on the start time

     Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

     List<int[]> result = new ArrayList<>();

     int[] currentInterval = intervals[0];

     for (int i = 1; i < intervals.length; i++) {

       if (intervals[i][0] <= currentInterval[1]) {

         // Merge overlapping intervals

         currentInterval[1] = Math.max(currentInterval[1], intervals[i][1]);

       } else {

         // Add a non-overlapping interval to the result

         result.add(currentInterval);

         currentInterval = intervals[i];

       }

     }

     // Add the last interval

     result.add(currentInterval);

     return result.toArray(new int[result.size()][]);

   }

   public static void main(String[] args) {

     int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};

     int[][] merged = mergeIntervals(intervals);

     System.out.println("The merged intervals are: “ + Arrays.deepToString(merged));

   }

}

Output:

The merged intervals are : [[1, 6], [8, 10], [15, 18]]

Complexity analysis: The naive approach for merging overlapping intervals has a higher time complexity than the optimized sorting-based approach. The outer loop runs until no more merges are possible, with a worst-case time complexity of O(n). The inner loop runs through all pairs of intervals in the list, with a worst-case time complexity of O(n^2). The above naive approach is less efficient than the optimized sorting-based approach.

Using Optimized Approach

The optimized approach efficiently merges overlapping intervals by sorting them based on start times and then iterating through the sorted intervals. If there is an overlap, the current interval is updated to the maximum of the current end time and the end time of the overlapping interval. If no overlap occurs, the non-overlapping interval is added to the result. The last interval is added to the result.

Here's the implementation to merge intervals using an optimized approach:

FileName:MergeIntervals1.java

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

public class MergeIntervals1 {

   public static int[][] mergeIntervals(int[][] intervals) {

     if (intervals == null || intervals.length <= 1) {

       return intervals;

     }

     // Sort intervals based on the start time

     Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

     List<int[]> result = new ArrayList<>();

     int[] currentInterval = intervals[0];

     for (int i = 1; i < intervals.length; i++) {

       if (intervals[i][0] <= currentInterval[1]) {

         // Merge overlapping intervals

         currentInterval[1] = Math.max(currentInterval[1], intervals[i][1]);

       } else {

         // Add a non-overlapping interval to the result

         result.add(currentInterval);

         currentInterval = intervals[i];

       }

     }

     // Add the last interval

     result.add(currentInterval);

     return result.toArray(new int[result.size()][]);

   }

   public static void main(String[] args) {

     int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};

     int[][] merged = mergeIntervals(intervals);

     System.out.println("The merged intervals are : " + Arrays.deepToString(merged));

   }

}

Output:

The merged intervals are : [[1, 6], [8, 10], [15, 18]]

Complexity analysis: The optimized approach for merging overlapping intervals has a time complexity of O(n log n) due to the sorting step, which takes O(n log n) time. The loop iterates through the sorted intervals, contributing to the overall time complexity of O(n log n). The space complexity is O(n) due to the additional space needed for the result list.

← Prev Next →

Merge Intervals Problem in Java

Using Naive Approach

Using Optimized Approach