3169. Count Days Without Meetings - Medium

前往題目

想法

• 最直觀的就是用set裝滿天數，然後用所有的meetings去排除，最後看size，但很明顯的這太慢了，每個區間有n天，然後有n個區間，就要n^n次了

思路

1. 先依照starting day排序
2. 然後檢查每個區間是否和上一個重疊
3. 是就合併，否則紀錄天數
4. 最後天數減去總天數就是答案

Code

網友解答

class Solution {
    public int countDays(int days, int[][] meetings) {
        // Sort the meetings by start day
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);

        int totalMeetingDays = 0;

        int s = meetings[0][0]; // Start day
        int e = meetings[0][1]; // End day

        // Start to merge and record total meeting days
        for (int i = 1; i < meetings.length; ++i) {
            // Need to merge (- 1 for continuous meetings)
            if (e >= meetings[i][0] - 1) {
                e = Math.max(e, meetings[i][1]);
            } else {
                // Update the meeting days
                totalMeetingDays += e - s + 1;
                // Update the interval to the next meeting
                s = meetings[i][0];
                e = meetings[i][1];
            }
        }

        // Add the last meeting
        totalMeetingDays += e - s + 1;

        return days - totalMeetingDays;
    }
}