Posts Merge Intervals
Post
Cancel

Merge Intervals

PROBLEM DESCRIPTION

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.

leetcode

SOLUTION

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {

    public int[][] merge(int[][] intervals) {

        //sort based on start of the intervals
        Arrays.sort(intervals, (o1, o2) -> o1[0] > o2[0]?1: (o1[0] < o2[0]?-1:0) );

        List<int[]> list = new ArrayList<>();

        //init
        list.add(intervals[0]);

        //start merging from index 1
        for(int i=1; i<intervals.length; i++){

            //Get the end of last added interval
            int previousEnd = list.get(list.size()-1)[1];

            //If the previously added interval's end is more than or equal to the current interval's start, then we should merge them
            if(previousEnd >= intervals[i][0]){
                //to merge them, we can just update the end of previous interval which was added by max(previousEnd, currentEnd)
                list.get(list.size()-1)[1] = Math.max(previousEnd, intervals[i][1]);
            }else{
                //if they don't merge, add this new interval
                list.add(intervals[i]);
            }

        }

        //convert to int[][]
        int[][] ans = new int[list.size()][2];
        for(int i=0; i<list.size(); i++){
            ans[i] = list.get(i);
        }

        // we can also do:
        // return list.toArray(new int[list.size()][]);
        return ans;

    }

}
This post is licensed under CC BY 4.0 by the author.