DDSA Solutions

3169. Count Days Without Meetings

MediumView on LeetCode
ArraySorting
Time: O(m log m)
Space: O(1)

Problem Overview

Count days in [1, days] with no meetings.

Advertisement

Intuition

Count days in [1, days] with no meetings. Sort meeting intervals, sweep in order, and add gap lengths between non-overlapping busy spans. After the last meeting, add remaining free days until day `days`. Overlapping meetings merge implicitly by tracking prevEnd.

Algorithm

  1. 1Sort meetings by start day.
  2. 2freeDays = 0, prevEnd = 0.
  3. 3For each [start, end]: if start > prevEnd + 1, add start - prevEnd - 1 to freeDays.
  4. 4Set prevEnd = max(prevEnd, end).
  5. 5After loop: add max(0, days - prevEnd) for trailing free days.
  6. 6Return freeDays.

Example Walkthrough

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

  1. 1.Sorted: [1,3],[5,7],[9,10]. Gap before 5: day 4. After day 7 until 9: day 8. None after 10.

Output: 2

Common Pitfalls

  • •Meetings are inclusive [start, end] — gap between prevEnd and next start is start - prevEnd - 1.
  • •Overlapping meetings: prevEnd = max(prevEnd, end) without double-counting busy days.
  • •Do not subtract from days naively without handling overlaps.
3169.cs
C#
// Approach: Sort and merge meeting intervals; subtract covered ranges from total days.
// Time: O(m log m) Space: O(1)

public class Solution
{
    public int CountDays(int days, int[][] meetings)
    {
        int freeDays = 0;
        int prevEnd = 0;

        Array.Sort(meetings, (a, b) => a[0].CompareTo(b[0]));

        foreach (var meeting in meetings)
        {
            int start = meeting[0];
            int end = meeting[1];
            if (start > prevEnd)
                freeDays += start - prevEnd - 1;
            prevEnd = Math.Max(prevEnd, end);
        }

        return freeDays + Math.Max(0, days - prevEnd);
    }
}
Advertisement
Was this solution helpful?

Related Problems