LeetCode - 3169. Count Days Without Meetings

문제링크

 

문제 설명

직원이 근무할 수 있는 총 일수를 나타내는 양의 정수 days가 주어집니다 (1일부터 시작).
또한, 크기가 n인 2차원 배열 meetings가 주어지며,
meetings[i] = [start_i, end_i]는 i번째 회의가 시작되는 날과 끝나는 날(양 끝 포함)을 나타냅니다.

직원이 근무 가능한 날 중, 회의가 잡히지 않은 날의 수를 반환하세요.

🔸 회의는 겹칠 수 있습니다. (즉, 동일한 날에 여러 회의가 잡힐 수 있음)

제한 사항

• 1 <= days <= 10^9
• 1 <= meetings.length <= 10^5
• meetings[i].length == 2
• 1 <= meetings[i][0] <= meetings[i][1] <= days

예시

Example 1:

Input: days = 10, meetings = [[5,7],[1,3],[9,10]]

Output: 2

Explanation:

There is no meeting scheduled on the 4th and 8th days.

 

Example 2:

Input: days = 5, meetings = [[2,4],[1,3]]

Output: 1

Explanation:

There is no meeting scheduled on the 5th day.

 

Example 3:

Input: days = 6, meetings = [[1,6]]

Output: 0

Explanation:

Meetings are scheduled for all working days.

풀이 흐름

• 처음에는 boolean[] tmp를 선언해서 meetings를 돌면서 start_i ~ end_i까지 true로 세팅한 뒤 마지막에 tmp에서 false의 개수를 세면 되지 않을까 생각했습니다. 하지만 days의 범위가 10^9이기 때문에 시간 초과가 발생할 것 같아 다른 방법을 찾았습니다.
• 우선 meetings를 정렬하면 어떨까 생각했습니다. 이 부분은 경험적인 생각의 흐름으로 주어진 배열 요소의 순서가 중요한 문제가 아니면 일반적으로 정렬을 하는 편이 더 생각하기 유리했습니다.
• 그 뒤 정렬한 meetings를 돌면서 현재 인덱스에서 가장 늦게 끝나는 회의 시간을 구하면서 만약 다음 회의 시작 시간과 가장 늦게 끝나는 회의 시간 사이에 텀이 존재하면 그 텀만큼 더해주면 되지 않을까 생각했습니다.
• 아래 코드에서는 가장 늦게 끝나는 회의 시간의 인덱스를 저장하고 있지만 단순히 가장 늦게 끝나는 회의 시간을 저장하여 사용하는 방식이 더 이해하기 쉬운 코드일 것 같습니다.

코드

import java.util.*;

class Solution {
    public int countDays(int days, int[][] meetings) {
        Arrays.sort(meetings, (m1, m2) -> {
            if (m1[0] != m2[0]) {
                return m1[0] - m2[0];
            }
            return m1[1] - m2[1];
        });
        int count = meetings[0][0] - 1;
        int idx = 0;
        for (int i = 1; i < meetings.length; i++) {
            if (meetings[idx][1] >= meetings[i][0]) {
                if (meetings[idx][1] < meetings[i][1]) {
                    idx = i;
                }
                continue;
            }
            count += meetings[i][0] - meetings[idx][1] - 1;
            idx = i;
        }
        if (meetings[idx][1] < days) {
            count += days - meetings[idx][1];
        }
        return count;
    }
}