# Merge overlapping intervals challenge

**Problem statement**

Given a set of intervals in any order merge the overlapping intervals and return the list of merged intervals.

**Sample input**

[{6,8} {2,4} {1,3} {5,5} {-1,4} {3,4} {6,8} {8,10}]

**Sample output**

[{-1,4} {5,5} {6,10}]

**Solution**

The first step we are going to take is sort the intervals in ascending order based on their ending time.

Next, we are going to traverse over the sorted list and as long as two adjacent intervals and overlap () we keep merging them by taking as the new and as the new for our new interval.

Once no more adjacent intervals are *merging* we add the newly created interval to our new list and resume the traversal until we have visited all intervals in the original list.

**Full code**

public class MergeIntervals { private static Listmerge(List intervals) { List ans = new ArrayList<>(); // Sort in ASC order depending on their ending time. Collections.sort(intervals, new Comparator () { /** * This method returns zero if the objects are equal. * It returns a positive value if interval1 is greater than interval2. * Otherwise, a negative value is returned. */ @Override public int compare(Integer[] interval1, Integer[] interval2) { return interval1[1] - interval2[1]; } }); int n = intervals.size(); Integer[] cur = intervals.get(0); int i = 1; while (i < n) { Integer[] next = intervals.get(i); while (next[0] <= cur[1] && i < intervals.size()) { cur[0] = Math.min(cur[0], next[0]); cur[1] = next[1]; i++; if (i < intervals.size()) { next = intervals.get(i); } } ans.add(cur); cur = next; } return ans; } public static void main(String[] args) throws FileNotFoundException { List intervals = new ArrayList<>(); intervals.add(new Integer[]{6, 8}); intervals.add(new Integer[]{2, 4}); intervals.add(new Integer[]{1, 3}); intervals.add(new Integer[]{5, 5}); intervals.add(new Integer[]{-1, 4}); intervals.add(new Integer[]{3, 4}); intervals.add(new Integer[]{6, 8}); intervals.add(new Integer[]{8, 10}); System.out.println("Not merged:"); for (Integer[] interval : intervals) { System.out.print("{" + interval[0] + "," + interval[1] + "} "); } List result = merge(intervals); System.out.println("\n\nMerged:"); for (Integer[] interval : result) { System.out.print("{" + interval[0] + "," + interval[1] + "} "); } } }