DEV Community

Cover image for Merge Intervals
Tisha Agarwal
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].

To solve the question click here:(https://leetcode.com/problems/merge-intervals/)

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[0]-o2[0];
});

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[0]-o2[0];
        });

        Stack<int[]> st=new Stack<>();
        st.push(intervals[0]);//[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[0]<=last_inserted[1])
             {
                 st.pop();
                 st.push(new int[]{last_inserted[0],Math.max(last_inserted[1],current[1])});
             }
             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()][2];
        st.toArray(res);
        System.out.println("----------");
        for(int i=0;i<res.length;i++)
        {
          System.out.print("["+res[i][0]+",");
          System.out.print(res[i][1]+"]"+" ");
        }
    }
Enter fullscreen mode Exit fullscreen mode

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][2];

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

        int start=intervals[0][0];// start=1
        int last=intervals[0][1]; //end=3

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

Discussion (3)

Collapse
lexlohr profile image
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][1] = index
    } else if (on && !last) {
      merged.push([index, index])
    }
    return merged
  }, [])
Enter fullscreen mode Exit fullscreen mode

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

Collapse
hima_khaitan profile image
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.
Enter fullscreen mode Exit fullscreen mode
Collapse
tishaag098 profile image
Tisha Agarwal Author

Thank you and would keep that in mind!