LeetCode：3169

前言

解週賽遇到一題覺得實用性頗高的題目

思路與答案

題目：

leetCode link

有一段固定期間，ex: 10 天，並給數個會議區間，ex: [[5,7],[1,3],[9,10]]，求不用開會的時間。

Note: 會議區間可能會重疊

想法：

一開始想的是將所有會議日期列出來，然後刪掉之後剩下的部分就是答案。


var countDays = function (days, meetings) {
    let temp = []
    for(let i = 0; i < meetings.length; i++){
      let [start,end] = meetings[i]
      for(let v = start; v <= end; v++) {
        temp.push(v)
      }
    }
    return days - Array.from(new Set(temp)).length
}

但是這樣會是一個 O(n^2) 的解法，所以要想怎麼樣可以優化成 O(n)。

之前的想法是如何找出會議區間中間的數字，所以複雜度提升了一個 for 迴圈，如果不用迴圈，那只知道這個會議區間會進行幾天，ex: [5,7] 是 7-5 + 1，5,6,7 三天，這樣為了避免重複扣掉重疊的區間，必須要先做排序。


var countDays = function (days, meetings) {
    meetings.sort((a, b) => a[0] - b[0]);
    let temp = 0
    let noMeetingDays = days
    for (let i = 0; i < meetings.length; i++) {
        let [start, end] = meetings[i]
        if (start > temp) {
            noMeetingDays -= end - start + 1
        }
        temp= end
    }
    return noMeetingDays
};

最後就剩下一個重疊區間的問題，ex: [[1,3],[1,10]]，會因為 1 已經被計算過了被忽略掉，所以要把這段邏輯加進去，並更新 temp 的計算規則。

var countDays = function (days, meetings) {
    meetings.sort((a, b) => a[0] - b[0]);
    let temp = 0
    let noMeetingDays = days
    for (let i = 0; i < meetings.length; i++) {
        let [start, end] = meetings[i]
        if (start > temp) {
            noMeetingDays -= end - start + 1
        } else if (end > temp) {
            noMeetingDays -= end - temp
        }
        temp = Math.max(end, temp)
    }
    return noMeetingDays
};

覺得如果需要處理日曆，排程這類需求的時候可能都用的到這個處理方式，因此紀錄一下。