# 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.

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.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, interval);
}
Collections.sort(intervalList);
System.out.println("Sorted Intervals" + intervalList);
for (Interval interval: intervalList) {
if (merged.isEmpty()) {
} else {
Interval lastInterval = merged.getLast();
if (lastInterval.end < interval.start) {
} else {
/*Input: [[1,4],[2,3]]
Expected: [[1,4]]*/
lastInterval.end = Math.max(merged.getLast().end, interval.end);
}
}
}
int[][] result = new int[merged.size()];
int i = 0;
for (Interval interval: merged) {
result[i] = interval.start;
result[i] = 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] + "-" + arr[i] + " || ");
}
}
}
```
```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