Given an array of intervals where intervals[i] = [start-i, end-i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Overview

Solution

It’s is important to start with sorting the intervals array. Sorting, will give us the ability to detect intervals by:

• Checking each element for the end value and compare with the next interval start value
• If the end value of an interval is greater than or equal to the start of the next interval, we have a overlap that we need to merge

Time Complexity

The time complexity of this algorithm is O(nlog(n)) as we need to sort the array. All other operations are less.

Space Complexity

Space complexity is O(n), because we are storing the merged intervals in a new array and in the worst case scenario there may not be any intervals and we would need to store all elements.

Java Source Code

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

        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
        final List<int[]> mergedIntervals = new ArrayList<>();
        var currentInterval = intervals[0];
        mergedIntervals.add(currentInterval);

        for (var nextInterval : intervals) {
            var currentIntervalEnd = currentInterval[1];
            var nextIntervalStart = nextInterval[0];
            var nextIntervalEnd = nextInterval[1];

            if (currentIntervalEnd >= nextIntervalStart) {
               currentInterval[1] = Math.max(currentIntervalEnd,nextIntervalEnd);
            } else {
                currentInterval = nextInterval;
                mergedIntervals.add(currentInterval);
            }
        }
        return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
    }

Conclusion

Eventually, all things merge into one, and a river runs through it.

Norman Maclean