Merge Intervals

Problem Statement:

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 1: 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] overlap, merge them into [1,6].

Example 2: Input: intervals = [[1,4],[4,5]] Output: 1,5 Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints: 1 <= intervals.length <= 10^4 intervals[i].length == 2 0 <= starti <= endi <= 10^4

Solution:

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> output = new ArrayList<>();
 
        // Sort intervals based on the starting point
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
 
        // Add the first interval to the output list
        output.add(intervals[0]);
 
        // Iterate through each interval
        for (int[] interval : intervals) {
            // Get the start and end of the last interval in the output list
            int lastStart = output.get(output.size() - 1)[0];
            int lastEnd = output.get(output.size() - 1)[1];
            
            // Get the start and end of the current interval
            int start = interval[0];
            int end = interval[1];
 
            // Check if there is an overlap with the last interval in the output list
            if (lastEnd >= start) {
                // Merge the intervals by updating the start and end
                start = Math.min(start, lastStart);
                end = Math.max(end, lastEnd);
                // Remove the last interval from the output list
                output.remove(output.size() - 1);
                // Add the merged interval to the output list
                output.add(new int[]{start, end});
            } else {
                // If there is no overlap, add the current interval to the output list
                output.add(interval);
            }
        }
        // Convert the output list to a 2D array and return
        return output.toArray(new int[output.size()][]);
    }
}