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.

<解題>

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals == null || intervals.length<=1){
            return intervals;
        }
        Arrays.sort(intervals, (arr1,arr2)->Integer.compare(arr1[0],arr2[0]));

        List<int[]> output_arr = new ArrayList();
        int[] current_interval = intervals[0];
        output_arr.add(current_interval);

        for(int[] interval : intervals){
            int current_begin = current_interval[0];
            int current_end = current_interval[1];
            int next_begin = interval[0];
            int next_end = interval[1];
            if(current_end >= next_begin){
                current_interval[1] = Math.max(current_end, next_end);
            } else{
                current_interval = interval;
                output_arr.add(current_interval);
            }
        }
        return output_arr.toArray(new int[output_arr.size()][]);
    }
}

Time: O(n log n) -> 快速排序的平均時間複雜度為 O(n log n) Space: O(n)

1. the Arrays.sort function is used to sort the intervals array using quicksort. The average time complexity of quicksort is O(n log n), where n is the number of intervals.
2. the code iterates through the sorted array of intervals once to perform the merging operation. The operations performed during this traversal are linear, so the time complexity is O(n).

length vs size()

在Java中，.length 和 .size() 是用來獲取集合（陣列、ArrayList等）的大小或元素個數的方式，但它們的使用情境不同，取決於你正在處理的數據結構。

.length：

.length 是一個數組的屬性，用於獲取數組的長度，也就是數組中元素的個數。 它通常用於原生數組（例如 int[]、double[]）或多維數組，因為這些數組具有固定的大小，無法改變。 例如，int[] arr = new int[5]; int length = arr.length; 用於獲取數組 arr 的長度，此處 length 將為5。 .size()：

.size() 是用於獲取集合類（例如ArrayList、List等）的方法，用於獲取集合中元素的個數。 它通常用於集合類，因為這些類可以根據需要動態調整大小，所以 .size() 返回的是當前集合中的元素個數。 例如，ArrayList list = new ArrayList<>(); int size = list.size(); 用於獲取ArrayList list 中元素的個數，此處 size 將一開始為0。