Problem of The Day: Count Days Without Meetings

Problem Statement

Brute Force [MLE]

class Solution:
    def countDays(self, days: int, meetings: List[List[int]]) -> int:
        working_days = set()
        res = 0
        for meeting in meetings:
            working_days.update(range(meeting[0], meeting[1] + 1))

        for day in range(1, days + 1):
            if day not in working_days:
                res += 1
        return res

Following hint approach

class Solution:
    def countDays(self, days: int, meetings: List[List[int]]) -> int:
        res = 0
        meetings.sort()
        N = len(meetings)
        temp = [meetings[0]]
        for i in range(1, N):
            start, end = meetings[i]
            prev_start, prev_end = temp[-1]
            if start <= prev_end:
                start = min(start, prev_start)
                end = max(end, prev_end)
                temp[-1][0] = start
                temp[-1][1] = end
            else:
                temp.append([start, end])

        res += (temp[0][0] - 1)

        if temp[-1][1] < days:
            res += (days - temp[-1][1])

        for i in range(len(temp) - 1):
            curr_end = temp[i][1]
            next_start = temp[i + 1][0]
            res += (next_start - curr_end) - 1

        return res

Editorial

Approach 1: Line Sweep

class Solution:
    def countDays(self, days: int, meetings: list[list[int]]) -> int:
        day_map = defaultdict(int)
        prefix_sum = 0
        free_days = 0
        previous_day = days
        has_gap = False

        for meeting in meetings:
            # Set first day of meetings
            previous_day = min(previous_day, meeting[0])

            # Process start and end of meeting
            day_map[meeting[0]] += 1
            day_map[meeting[1] + 1] -= 1

        # Add all days before the first day of meetings
        free_days += previous_day - 1
        for current_day in sorted(day_map.keys()):
            # Add current range of days without a meeting
            if prefix_sum == 0:
                free_days += current_day - previous_day
            prefix_sum += day_map[current_day]
            previous_day = current_day

        # Add all days after the last day of meetings
        free_days += days - previous_day + 1
        return free_days

Approach 2: Sorting

class Solution:
    def countDays(self, days: int, meetings: list[list[int]]) -> int:
        free_days = 0
        latest_end = 0

        # Sort meetings based on starting times
        meetings.sort()

        for start, end in meetings:
            # Add current range of days without a meeting
            if start > latest_end + 1:
                free_days += start - latest_end - 1

            # Update latest meeting end
            latest_end = max(latest_end, end)

        # Add all days after the last day of meetings
        free_days += days - latest_end

        return free_days