2023-06-03 刷题

练习英文描述算法

56. 合并区间 - 力扣（LeetCode） [mid, 非常好展示思路]

分析：

• First sort the intervals by start time, so that we can easily find which intervals can be merged by checking intervals from left to right.
• Use one example to demo the process. (e.g. use java comment, to show the merging process.).

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        List<int[]> answer = new ArrayList<>();
        for (int[] interval: intervals) {
            int start = interval[0], end = interval[1];
            if (answer.isEmpty() || answer.get(answer.size() - 1)[1] < start) { // no overlap
                answer.add(interval);
            } else {
                int[] last = answer.get(answer.size() - 1);
                last[1] = Math.max(last[1], end);
            }
        }
        return answer.toArray(new int[answer.size()][2]); // keep in mind
    }
}
/*
    [[1,3],[2,6],[8,10],[15,18]]
cur:                              |


answer: [[1,6], [8, 10], [15, 18]]
    has overlap:  last.end >= cur.start, update last.end
       last.end = max(last.end, cur.end)
    no overlap:  add it to answer
*/

57. 插入区间 - 力扣（LeetCode） 【mid，非常容易困惑】

// 一种比较优雅的写法
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> answer = new ArrayList<>();
        for (int[] cur : intervals) {
            if (newInterval == null || cur[1] < newInterval[0]) { // left part
                answer.add(cur);
            } else if (newInterval[1] < cur[0]) { // right part, first one
                answer.add(newInterval);
                answer.add(cur);
                newInterval = null;
            } else { // middle overlap
                newInterval[0] = Math.min(newInterval[0], cur[0]);
                newInterval[1] = Math.max(newInterval[1], cur[1]);
            }
        }
        if (newInterval != null) {  // newInterval very long
            answer.add(newInterval);
        }
        return answer.toArray(new int[answer.size()][2]);
    }
}
/*
     [[1,2],   [3,5],[6,7],[8,10],   [12,16]]
cur:   left       middle               right
     cur[1] < start
                 start <= cur[1] &&
                 end >= cur[0]
                                      cur[0] > end

newInterval = [3,8]  (start, end) 

coding skill detail:
    handle the middle part is complex, the condition is complex.
    so why not handle left, right first, then the remaining is the middle.
        left part is easy to coding.
        how to know right part starts?  checking first one in the right part, then
            mark interval as null, so that we can add it directly.
        otherwise, merge newInterval with current one

In summary, we handle three cases in the loop body: 
	add left, part of right part
	add first of right part (& newInterval)
	merge middle
after loop, need to consider, newInterval is not added if it is too long.
*/

另外一种写法，就是分成三段，用下标，这种写法也更清楚一点吧，虽然长一点，但是性能更好：

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> ans = new ArrayList<>();
        int i = 0, n = intervals.length;
        int start = newInterval[0], end = newInterval[1];
        for (; i < n && intervals[i][1] < start; i++) { // left part
            ans.add(intervals[i]);
        }
        // middle, handle overlap
        for(; i < n && intervals[i][0] <= end; i++) {
            start = Math.min(start, intervals[i][0]);
            end = Math.max(end, intervals[i][1]);
        }
        ans.add(new int[] {start, end});
        
        for(; i < n; i++) { // right part
            ans.add(intervals[i]);
        }

        return ans.toArray(new int[ans.size()][2]);
    }
}
/*
     [[1,2],   [3,5],[6,7],[8,10],   [12,16]]
cur:   left       middle               right
     cur[1] < start
                 start <= cur[1] &&
                 end >= cur[0]
                                      cur[0] > end

newInterval = [3,8]  (start, end) 
*/

1272. 删除区间 - 力扣（LeetCode） [mid, 细节太多了]

分析：

• 看到一个非常好的写法，借鉴一下。这个跟57的insertInterval有一点不同。可以直接处理左右不相交的部分。对于overlap的部分，考虑最后还剩下哪些比较好。画图能清晰说明这个问题。比自己在纸上写要快很多，而且直观。

class Solution {
    public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
        List<List<Integer>> ans = new ArrayList<>();
        for (int[] cur : intervals) {
            // left no overlap & right no overlap
            if (cur[1] < toBeRemoved[0] || cur[0] > toBeRemoved[1]) {
                ans.add(Arrays.asList(cur[0], cur[1]));
            } else { // has overlap
                if (cur[0] < toBeRemoved[0]) {
                    ans.add(Arrays.asList(cur[0], toBeRemoved[0]));
                }
                if (cur[1] > toBeRemoved[1]) { 
                    ans.add(Arrays.asList(toBeRemoved[1], cur[1]));
                }
            }
        }

        return ans;
    }
}

/*
   [[-5,-1],   [0,2],[3,4],[5,7],   [9,12]],   [1,6] --> (start, end)
cur                                   |
  left: cur.end < start
                   overlap (handle it): part of it overlap, includeded (may be multiple)
                                 right: cur.start > end
---  ---- --- ----  ------
        =========

--------
  ===

------
==

-----
  ===
*/

要考虑：区间端点相等的情况。这题如果直接思考overlap的几个部分，会很困难。

参考资料：

• https://www.bilibili.com/video/BV1Po4y1Z7sm