[LeetCode] 3169. Count Days Without Meetings (Python)

 

 

난이도: Medium

Problem Description

---

You are given a positive integer days representing the total number of days an employee is available for work (starting from day 1). You are also given a 2D array meetings of size n where, meetings[i] = [start_i, end_i] represents the starting and ending days of meeting i (inclusive).

 

Return the count of days when the employee is available for work but no meetings are scheduled.

 

Note: The meetings may overlap.

 

Problem Example

---

Example 1:

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

Output: 2

Explanation:

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

 

Example 2:

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

Output: 1

Explanation:

There is no meeting scheduled on the 5^th day.

 

Example 3:

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

Output: 0

Explanation:

Meetings are scheduled for all working days.

 

Constraints

---

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

 

✏️ Solution

---

class Solution:
    def countDays(self, days: int, meetings: List[List[int]]) -> int:
        meetings.sort()

        for i in range(1, len(meetings)):
            current_start, current_end = meetings[i]
            prev_start, prev_end = meetings[i-1]

            if current_start <= prev_end:
                meetings[i][0] = prev_start
                meetings[i][1] = max(current_end, prev_end)
            
            if prev_start != meetings[i][0]:
                days -= (prev_end - prev_start + 1)
    
        return days - (meetings[-1][1] - meetings[-1][0] + 1)

처음에는 start에 1 end+1에 -1을 넣고 마지막에 누적합을하여 0의 갯수를 세는 코드를 작성했지만, Memory Limit Exceed가 발생했다.

 

생각해보니 굳이 배열을 안만들고 end - start + 1을 하면 빠지는 날을 구할 수 있다.

이를 위해 meetings에 있는 날짜들에 대해 합칠 수 있으면 합쳐야겠다고 생각했다.

 

예를 들어 [[1,4], [2,3]] 다음과 같이 meetings에 들어있다면, 결국 1 ~ 4가 미팅이 잡힌 날짜인 것이다.

 

따라서, meetings를 정렬시켜주고 이전에 끝나는 날짜와 현재 시작 날짜를 비교하여 끝나는 날짜가 더 크다고 한다면 현재를 [이전 시작 날짜, max(이전 끝 날짜, 현재 끝 날짜)]로 업데이트 했다.

 

ex)

i-1 = [1,4]

i = [2, 3]

 

meetings[i-1][1] >= meetings[i][0]  # 4 >= 2

meetings[i] = [meetings[i-1][0], max(meetings[i][1], meetings[i-1][1]) # [1, 4]

 

 

업데이트를 하고 나서 현재 시작 날짜와 이전 시작 날짜가 다르다고한다면 이 날짜들은 병합이 되지 않는 것이기 때문에 days - 이전 끝 날짜 - 이전 시작 날짜 + 1을 통해 일을 못하는 날을 전체 days에서 빼주었다.

 

위 과정을 meetings 끝까지 반복한다.

 

반복문을 마치면 days - (meetings[-1][i] - meetings[-1][0] + 1)을 통해 최종 답을 반환하였다.

 

⚙️ Runtime & Memory

---

 

 

---

문제: 3169. Count Days Without Meetings

 

 

깃허브: github

algorithmPractice/LeetCode/3430-count-days-without-meetings at main · laewonJeong/algorithmPractice