Merge overlapping Intervals

Given a collection of Intervals, the task is to merge all of the overlapping Intervals.

Let {{1,3},{2,4},{6,8},{9,10}} be the set of input intervals. Here, {1,3} and {2,4} is an overlapping interval. Hence it will be merged into one interval i.e. {1,4}.

Hence, the final merged intervals will be {{1, 4}, {6, 8}, {9, 10}}.

Approach

The simple approach to this problem is : 

Step 1 : Sort the input array of intervals to group the closer intervals together.

Step 2 : Create an answer array to store the merged intervals.

Step 3 : Add the first interval to the answer array.

Step 4 : Iterate the input array and check which one of the following conditions is true : 

1. If the current interval overlaps with the last inserted interval in the answer array : If the last inserted interval’s end is greater than the current interval, then it indicates that the intervals overlap. In such cases, update the end of the last inserted interval with the maximum(current interval’s end, last inserted interval’s end).
2. Else if the current interval does not overlap with the last inserted interval : Insert the current interval into the answer array.

Step 5 : Iterate until the all the intervals in the input array are checked for above conditions and return the answer array.

Complexity

• Time Complexity: O(N*logN) + O(N), where N = the size of the given array.
• Space Complexity:  O(N)

Java Code

import java.util.Arrays;
import java.util.List;
import java.util.*;


public class MergeIntervals {


    public static List<List<Integer>> mergeOverlappingIntervals(int[][] arr) {
        int n = arr.length; // size of the array
        //sort the given intervals:
        Arrays.sort(arr, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });


        List<List<Integer>> ans = new ArrayList<>();


        for (int i = 0; i < n; i++) {
            // if the current interval does not
            // lie in the last interval:
            if (ans.isEmpty() || arr[i][0] > ans.get(ans.size() - 1).get(1)) {
                ans.add(Arrays.asList(arr[i][0], arr[i][1]));
            }
            // if the current interval
            // lies in the last interval:
            else {
                ans.get(ans.size() - 1).set(1,
                     Math.max(ans.get(ans.size() - 1).get(1), arr[i][1]));
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        int[][] arr = {{1, 3}, {8, 10}, {2, 6}, {15, 18}};
        List<List<Integer>> ans = mergeOverlappingIntervals(arr);
        System.out.print("The merged intervals are: \n");
        for (List<Integer> it : ans) {
            System.out.print("[" + it.get(0) + ", " + it.get(1) + "] ");
        }
        System.out.println();
    }
}

Output

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