---

0. 문제

직원이 일할 수 있는 총 날짜 수를 나타내는 정수 days가 주어짐 (1일부터 시작). 또한, meetings라는 2차원 정수 배열이 주어짐. meetings[i] = [start_i, end_i]는 i번째 회의가 start_i일부터 end_i일까지 진행됨(양 끝 포함)을 의미함.

겹치지 않는 회의가 없는 날, 즉 직원이 일할 수 있지만 회의가 잡히지 않은 날의 수를 구하라.

회의 기간들은 겹칠 수 있음.

예제 1.

• 입력:
  days = 10, meetings = [[5,7],[1,3],[9,10]]
• 출력:
  2
• 설명:

  4일, 8일에 회의가 없어서 총 2일간 업무 가능

예제 2.

• 입력:
  days = 5, meetings = [[2,4],[1,3]]

• 출력:
  1

• 설명:

  5일에만 회의가 없음

예제 3.

• 입력:
  days = 6, meetings = [[1,6]]
• 출력:
  0
• 설명:

  모든 날에 회의가 있음

제한사항

1 <= days <= 109
1 <= meetings.length <= 105
meetings[i].length == 2
1 <= meetings[i][0] <= meetings[i][1] <= days

---

1. 풀이

1.1 단순

$O(Nm)$

class Solution {
    public int countDays(int days, int[][] meetings) {
    	// 날짜 별 회의 개수를 나타냄
        int[] meetingCount = new int[days + 1];

		// 각 회의 구간을 순회하면서 구간 내 모든 날짜에 표시
        for (int i = 0; i < meetings.length; i++) {
            for (int j = meetings[i][0]; j <= meetings[i][1]; j++) {
                meetingCount[j]++;
            }
        }
        
        int meetingFree = 0;
        // 표시되지 않은 날짜의 개수 확인
        for (int i = 1; i < meetingCount.length; i++)
            if (meetingCount[i] == 0)
                meetingFree++;
        return meetingFree;
    }
}

1.2 최적화

$O(N*logN)$

class Solution {
    public int countDays(int days, int[][] meetings) {
        //  각 구간의 시작일을 기준으로 정렬.
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);

        // 총 회의 일수
        int meetingCount = 0;

        // 회의 구간 초기화
        int merge_start = meetings[0][0];
        int merge_end = meetings[0][1];

        // 각 회의 구간 확인
        for (int i = 0; i < meetings.length; i++) {
            int start = meetings[i][0];
            int end = meetings[i][1];

            // 현재 확인 중인 구간이 기존 구간과 겹치는 상황
            // 정렬되어 있는 상태이기 때문에, merge_end와 start만 비교.
            if (merge_end >= start)
                merge_end = Math.max(merge_end, end);

            // 현재 확인 중인 구간이 기존 구간과는 별개인 상황.
            // 기존 구간의 길이를 총 회의 일수에 반영
            // 기존 구간을 신규 구간으로 재정의
            else {
                meetingCount += merge_end - merge_start + 1;
                merge_start = start;
                merge_end = end;
            }
        }
        // 마지막 구간은 반복문에 포함되지 않아, 별도로 반영.
        meetingCount += merge_end - merge_start + 1;

        // 전체 일수에서 회의 일수를 제외한 나머지를 반환
        return days - meetingCount;
    }
}