Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

If we sort the intervals by their start and end value, then each set of intervals that can be merged will appear as a contiguous “run” in the sorted list. Consider the following example of merging intervals.

Merge Intervals

First, we sort the list as described. Then, we insert the first interval into our merged list and continue considering each interval in turn as follows: If the current interval begins after the previous interval ends, then they do not overlap and we can append the current interval to merged. Otherwise, they do overlap, and we merge them by updating the end of the previous interval if it is less than the end of the current interval.

  1. Sort the intervals based on increasing order of start index. If the start indices are the same for two intervals then sort based on the end indices.
  2. Insert the first interval on to a LinkedList.
  3. For each interval do the following:
    1. If the current interval does not overlap with the last element of the LinkedList then insert it.
    2. If the current interval overlaps with the last element of the LinkedList then merge them by updating the end of the previous interval if it is less than the end of the current interval.
  4. In the end, the LinkedList contains the merged intervals.

Consider the following implementation:

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

class Interval implements Comparable <Interval> {

  int start;
  int end;

  public Interval(int start, int end) {
    this.start = start;
    this.end = end;
  }

  public int compareTo(Interval interval) {
    if (this.start == interval.start) {
      return this.end - interval.end;
    }
    return this.start - interval.start;
  }

  public String toString() {
    return "[" + start + "-" + end + "]";
  }
}

public class MergeInterval {

  public int[][] merge(int[][] intervals) {
    List <Interval> intervalList = new ArrayList <> ();
    for (int[] interval: intervals) {
      Interval in = new Interval(interval[0], interval[1]);
      intervalList.add( in );
    }
    Collections.sort(intervalList);
    System.out.println("Sorted Intervals" + intervalList);
    LinkedList <Interval> merged = new LinkedList <> ();
    for (Interval interval: intervalList) {
      if (merged.isEmpty()) {
        merged.add(interval);
      } else {
        Interval lastInterval = merged.getLast();
        if (lastInterval.end < interval.start) {
          merged.add(interval);
        } else {
          /*Input: [[1,4],[2,3]]
          Expected: [[1,4]]*/
          lastInterval.end = Math.max(merged.getLast().end, interval.end);
        }
      }
    }
    int[][] result = new int[merged.size()][2];
    int i = 0;
    for (Interval interval: merged) {
      result[i][0] = interval.start;
      result[i][1] = interval.end;
      i++;
    }
    return result;
  }
}

Test the Program:

public class TestMergeInterval {

  public static void main(String[] args) {
    int[][] intervals = {{0, 3}, {2, 6}, {8, 10}, {15, 18}, {0, 1}, {3, 7}, {0, 2}};
    MergeInterval mergeInterval = new MergeInterval();
    int[][] result = mergeInterval.merge(intervals);
    print(result);
  }

  private static void print(int[][] arr) {
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i][0] + "-" + arr[i][1] + " || ");
    }
  }
}
The output of the program is:
Sorted Intervals: [ [0-1], [0-2], [0-3], [2-6], [3-7], [8-10], [15-18]  
Merged Intervals: 0-7 || 8-10 || 15-18

Categories: Array

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s