Leetcode-3169. Count Days Without Meetings 题解

Intuition

To get meeting count, we just need to get dis-joint continous segments where meeting days are contained.

First sort this array, with order:
1.a[0] == b[0], compare a[1] > b[1]
2.a[0] < b[0], return -1;
3.a[0] > b[1], return 1;

Then travel in the sorted 2D array:

1. meeting[i+1][0] > meeting[i][1]: means the new segment started, add a segment to result.
2. meeting[i+1][0] <= meeting[i][1]:
   2.1 if meeting[i+1][1] > meeting[i][1]: merge the prev segment’s end to meeting[i+1][1], in other words, enlarge the prev segment.
   2.2 if meeting[i+1][1] > meeting[i][1]: means the prev segment contains the current segment, do nothing.
3. meeting[i+1][0] == meeting[i][1]: means the prev segment is adjacent to current segment, just check whether meeting[i+1][1] > meeting[i][1], if so, merge the prev segment’s end to meeting[i+1][1].

Total Time complexity is sorting cost: O(n*logn)

Approach

Complexity

• Time complexity:
• O(nlogn)

• Space complexity:
• O(n): The worst case is every segment length is 1 and all elements are in segments.

Code

// Runtime 61 ms Beats 100.00% of users with Java
// Memory 99.61 MB Beats 100.00% of users with Java
// Sort And get all dis-joint continous segment.
// T:O(nlogn), S:(n)
// 
class Solution {
    public int countDays(int days, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> a[0] != b[0] ? (a[0] - b[0]) : (a[1] != b[1] ? (a[1] - b[1]) : 0));
        List<List<Integer>> segment = new ArrayList<>();
        for (int[] meeting : meetings) {
            if (segment.isEmpty()) {
                List<Integer> list = new ArrayList<>();
                list.add(meeting[0]);
                list.add(meeting[1]);
                segment.add(list);
            } else {
                List<Integer> list = segment.get(segment.size() - 1);
                if (meeting[0] == list.get(1)) {
                    list.set(1, meeting[1]);
                } else if (meeting[0] < list.get(1)) {
                    if (meeting[1] > list.get(1)) {
                        list.set(1, meeting[1]);
                    }
                } else {
                    List<Integer> list2 = new ArrayList<>();
                    list2.add(meeting[0]);
                    list2.add(meeting[1]);
                    segment.add(list2);
                }
            }
        }
        int count = 0;
        for (List<Integer> segmentItem : segment) {
            count += segmentItem.get(1) - segmentItem.get(0) + 1;
        }

        return days - count;
    }
}