Scale Engineer

Count Days Without Meetings

Med
#2815Time: O(N * L + D), where N is the number of meetings, L is the average length of a meeting, and D is the total number of `days`. In the worst case, a meeting can span all `days`, making the complexity O(N * D). Given the constraints, this will result in a Time Limit Exceeded (TLE) error.Space: O(D), where D is the total number of `days`. We need a boolean array of size `days + 1`. Given the constraint `days <= 10^9`, this will cause a Memory Limit Exceeded (MLE) error.
Algorithms
Sorting
Data structures
Array

Prompt

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.

 

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.

 

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the days and meetings directly. We use a boolean array, where each index represents a day. We iterate through all meetings and mark the corresponding days in the array as busy. Finally, we count the number of days that were never marked.

Algorithm

  • Create a boolean array hasMeeting of size days + 1, and initialize all its elements to false.
  • Iterate through each meeting in the input meetings array.
  • For each meeting = [start, end], loop from i = start to end and set hasMeeting[i] = true.
  • Initialize a counter freeDays to 0.
  • Loop from i = 1 to days.
  • If hasMeeting[i] is false, it means the day is free, so increment freeDays.
  • After the loop, return freeDays.

Walkthrough

The core idea is to maintain a status for each day from 1 to days. A boolean array isMeetingDay of size days + 1 is used for this purpose, where isMeetingDay[i] will be true if there's a meeting on day i, and false otherwise.

First, we initialize the entire array to false. Then, we iterate through each meeting interval [start, end] provided in the meetings array. For each interval, we run a nested loop from start to end and set isMeetingDay[j] = true for all j in this range. This process marks all days that are covered by at least one meeting.

After processing all the meetings, we perform a final scan through the boolean array from day 1 to days. We count how many indices i still have isMeetingDay[i] as false. This count represents the total number of days without any scheduled meetings.

public int countDays(int days, int[][] meetings) {    if (days <= 0) {        return 0;    }    boolean[] hasMeeting = new boolean[days + 1];    for (int[] meeting : meetings) {        // Ensure meeting bounds are within the total days        int start = Math.max(1, meeting[0]);        int end = Math.min(days, meeting[1]);        for (int i = start; i <= end; i++) {            hasMeeting[i] = true;        }    }     int freeDays = 0;    for (int i = 1; i <= days; i++) {        if (!hasMeeting[i]) {            freeDays++;        }    }    return freeDays;}

Complexity

Time

O(N * L + D), where N is the number of meetings, L is the average length of a meeting, and D is the total number of `days`. In the worst case, a meeting can span all `days`, making the complexity O(N * D). Given the constraints, this will result in a Time Limit Exceeded (TLE) error.

Space

O(D), where D is the total number of `days`. We need a boolean array of size `days + 1`. Given the constraint `days <= 10^9`, this will cause a Memory Limit Exceeded (MLE) error.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly models the problem statement.

Cons

  • Extremely inefficient for large values of days.

  • Exceeds memory limits for days up to 10^9.

  • Exceeds time limits for days up to 10^9.

Solutions

class Solution {public  int countDays(int days, int[][] meetings) {    Arrays.sort(meetings, (a, b)->a[0] - b[0]);    int ans = 0, last = 0;    for (var e : meetings) {      int st = e[0], ed = e[1];      if (last < st) {        ans += st - last - 1;      }      last = Math.max(last, ed);    }    ans += days - last;    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem