Skip to Content

Merge overlapping intervals

Home | Coding Interviews | Greedy Algorithms | Merge overlapping 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.

class Solution {
    public int[][] merge(int[][] intervals) {
        
        //declaring an array list to store the pairs
        ArrayList<int[]> list=new ArrayList<>();
        
        //sorting the given interval array based on starting point
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);
        
        //defining start and end point
        int start=intervals[0][0];
        int end=intervals[0][1];
        
        //we will iterate through the 2d array intervals so in each iteration we will get a row[1D array] as i
        
        for(int[] i:intervals){
            //check if end point of 1st pair if greater than the starting point of the 2nd pair or not, basically we check it's in overlapping condition or not
            
            if(i[0]<=end){
                end=Math.max(end,i[1]);
            }
            
            //otherwise add it in the list
            else{
                list.add(new int[]{start,end});
                start=i[0];
                end=i[1];
            }
            
        }
        
        list.add(new int[]{start,end});
        return list.toArray(new int[0][]);
        
    }
}

Posted by Jamie Meyer 4 months ago

Related Problems

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals due to cooling time.

Return the minimum number of intervals required to complete all tasks.

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

0 <= j <= nums[i] and

i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].