56. Merge Intervals.md

56. Merge Intervals

---

leetcode Daily Challenge on November 18th, 2020.

---

Difficulty : Medium

Related Topics : Array、Sort

---

Given a collection of intervals, merge all overlapping intervals.

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

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Constraints:

• intervals[i][0] <= intervals[i][1]

---

Solution

• mine
  • Java
    • Runtime: 6 ms, faster than 60.40%, Memory Usage: 41.4 MB, less than 9.62% of Java online submissions

      // O(N*logN)time
      // O(N)space
      public int[][] merge(int[][] intervals) {
          Arrays.sort(intervals, (x1, x2) -> x1[0] - x2[0]);
          LinkedList<int[]> list = new LinkedList<>();
          for (int i = 0; i < intervals.length; i++) {
              if (!list.isEmpty() && list.getLast()[1] >= intervals[i][0]) {
                  list.getLast()[1] = Math.max(list.getLast()[1], intervals[i][1]);
              } else {
                  list.add(intervals[i]);
              }
          }
          int[][] res = new int[list.size()][];
          for (int i = 0; i < res.length; i++) {
              res[i] = list.removeFirst();
          }
          return  res;
      }
      

---