Leetcode — 56. Merge Intervals

The link to the problem: https://leetcode.com/problems/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 - 
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]] 
Since [1,3]與[2,6] are overlapped intervals, we can merge them to [1,6]

Thoughts:

So our first question will be, how do we determine whether two intervals are overlapped?
Assume we have interval A and interval B. (assume startA > startB)
When startB is greater than endA, it means that we don’t need to merge them since they are completely independent.
However, if startB ≤ endA, that means we can merge the two intervals.

⚠️ Since the problem doesn’t guarantee that the intervals are sorted by starting points, we need to sort the array before we using the logic to merge those intervals.

Code Logic:

After sorting the intervals, we can start to use the logic to choose whether to merge intervals.
First, we can use two variables to store the current start and end. These two variables will be the first pair of intervals that we are going to add to the list. (we can consider these as startA and endA)
While in the loop, we can consider the interval in the current position as intervalB. That is to say, we will compare startB with endA to decide whether we need to merge them.
If startB ≤ endA, we update the endA to the bigger end among endA and endB.
If we cannot merge interval A and B, what we do is add startA and endA into the list. Also, let interval B be our new interval A, so later we can check if the next interval needs to merge with our “interval A”.

After the loop, add interval A to the list and we’re done.

Below is my 5ms code that beats 94%:

public int[][] merge(int[][] intervals) {
        if(intervals.length<=1)
            return intervals;
        Arrays.sort(intervals,new Comparator<int[]>(){
            public int compare(int[] i1,int[] i2){
                return i1[0]-i2[0];
            }
        });
        int prevStart = intervals[0][0];
        int prevEnd = intervals[0][1];
        List<int[]> list = new ArrayList<>();
        for(int i = 1; i < intervals.length; i++)
        {
            int curStart = intervals[i][0];
            int curEnd = intervals[i][1];
            if(curStart <= prevEnd) //merge
                prevEnd = Math.max(prevEnd,curEnd);
            else
            {
                list.add(new int[]{prevStart,prevEnd});
                prevStart = curStart;
                prevEnd = curEnd;
            }
        }
        list.add(new int[]{prevStart,prevEnd});
        int[][] rst = new int[list.size()][];
        for(int i=0;i<rst.length;i++)
            rst[i] = list.get(i);
        
        return rst;
    }

If we didn’t include the time of sorting array in the beginning, both the time complexity and the space complexity are O(n).
The time complexity of the whole code is O(nlogn) i.e., the time of Arrays.sort()