[Uber] Merge overlapping Interval

Problem: Given a set of intervals, not necessarily in sorted order, merge all overlapping intervals into one.

Example:

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].

Approach:

1. Sort all intervals according to their start time, if start time is same then based on end time.
2. If current interval's start is lees than or equal to previous interval's end then we know that we can merge intervals. The new interval will be [previous interval' start, Max of current and previous end]. 
3. Else add the current interval to result.
4. Repeat 2-3 for every interval.

Implementation in C#:

    public int[][] Merge(int[][] intervals)

    {

        int length = intervals?.Length ?? 0;

        if (length <= 1)

        {

            return intervals;

        }

        Array.Sort(intervals, (i1, i2) => {

            int retVal = i1[0].CompareTo(i2[0]);

            if (retVal == 0)

            {

                return i1[1].CompareTo(i2[1]);

            }

            return retVal;

        });

        int currIndex = 0;

        for (int i = 1; i < length; ++i)

        {

            if (intervals[currIndex][1] >= intervals[i][0])

            {

                intervals[currIndex][1] = Math.Max(intervals[currIndex][1],

                                                   intervals[i][1]);

            }

            else

            {

                intervals[++currIndex] = intervals[i];

            }

        }

        int[][] result = new int[currIndex + 1][];

        Array.Copy(intervals, 0, result, 0, currIndex + 1);

        return result;

    }

Complexity: O(nlogn)