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]+"]"+" ");
        }
    }

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]+"]"+" ");
        }
    }
}

Comments

[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
  }, [])

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.

[Tisha Agarwal]

Thank you and would keep that in mind!