## DEV Community is a community of 871,688 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. Tisha Agarwal

Posted on • Updated on

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

The new thing that I learned in this question is about comparator interface in java. Using a comparator, we can sort the elements based on data members. For instance, it may be on roll no, name, age, or anything else.

In this question, I used comparator to sort the intervals according to the 1st interval.
```Arrays.sort(intervals,(o1,o2)->{ return o1-o2; });```
For eg:[2,4] [1,5] [7,19] [6,7] ------->[1,5] [2,4] [6,7] [7,19]

Approach 1:
Using Stack method

1. First I have created a stack and pushed the first interval in the stack.([1,3] is pushed in the stack st)
2. Then I iterated the loop from 2nd interval to the end of the array.

JAVA CODE

`````` public static void merge(int[][] intervals){

Arrays.sort(intervals,(o1,o2)->{
return o1-o2;
});

Stack<int[]> st=new Stack<>();
st.push(intervals);//[1,3] is pushed in the stack

for(int i=1;i<intervals.length;i++)
{
int[] current=intervals[i];
int[] last_inserted=st.peek();
if(current<=last_inserted)
{
st.pop();
st.push(new int[]{last_inserted,Math.max(last_inserted,current)});
}
else{
st.push(current);
}
}
// Stack<int[]> res=new Stack<>();
// while(st.size()>0)
// {
//     res.push(st.pop());
// }
// while(res.size()>0)
// {
//     System.out.println(res.pop());
// }
int[][] res = new int[st.size()];
st.toArray(res);
System.out.println("----------");
for(int i=0;i<res.length;i++)
{
System.out.print("["+res[i]+",");
System.out.print(res[i]+"]"+" ");
}
}
``````

Approach 2:
Used ArrayList to solve the problem in Space Complexity: O(n)

JAVA CODE

``````import java.util.*;
class merge_intervals{

public static void main(String[] args) throws Exception
{
Scanner sc=new Scanner(System.in);
System.out.print("Enter the number of elements: ");
int n=sc.nextInt();
int[][] arr=new int[n];

for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt();
arr[i]=sc.nextInt();
}
merge(arr);
}
public static void merge(int[][] intervals)
{
Arrays.sort(intervals,(o1,o2)->{
return o1-o2;
});
ArrayList<int[]> ans=new ArrayList<>();

int start=intervals;// start=1
int last=intervals; //end=3

for(int i=1;i<intervals.length;i++)
{
if(intervals[i]<=last && intervals[i]>=start)
{
last=Math.max(last,intervals[i]);
}
else
{
start=intervals[i];
last=intervals[i];
}
}
int[][] res=new int[ans.size()];
ans.toArray(res);
System.out.println("-----------------");
for(int i=0;i<ans.size();i++)
{
System.out.print("["+res[i]+",");
System.out.print(res[i]+"]"+" ");
}
}
}
``````

## Discussion (3) Alex Lohr

Not sure if in JS sorting isn't maybe even slower than a naive write and read approach:

``````const mergeIntervals = (intervals) => intervals
.reduce((set, [start, end]) => {
for (let index = start; index <= end; index++) {
set[index] = true
}
return set
}, [])
.reduce((merged, on, index, set) => {
const last = set[index - 1]
if (on && last) {
merged[merged.length - 1] = index
} else if (on && !last) {
merged.push([index, index])
}
return merged
}, [])
``````

Warning: array methods will skip empty parts of sparse arrays, which is why last cannot be taken from the last operation. Himanshu Khaitan

well written.

A suggestion though when you add

``````
js
after this mention the language so that dev.to can catch and highlight the synax accordingly.
``````