Count Days Without Meetings - Practice Coding Problems

Count Days Without Meetings - Problem

Array Sorting Medium

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.

Input & Output

Example 1 — Basic Case with Overlapping

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

› Output: 2

💡 Note: Meeting days are: 1,2,3 (first meeting), 5,6,7 (second meeting), 9,10 (third meeting). Free days are: 4,8. Total free days = 2.

Example 2 — No Meetings

$ Input: days = 4, meetings = []

› Output: 4

💡 Note: No meetings scheduled, so all 4 days (1,2,3,4) are free for work.

Example 3 — All Days Busy

$ Input: days = 3, meetings = [[2,4]]

› Output: 1

💡 Note: Meeting covers days 2,3. Only day 1 is free (day 4 is beyond the available days). Free days = 1.

Constraints

1 ≤ days ≤ 10⁹
0 ≤ meetings.length ≤ 1000
1 ≤ start_i ≤ end_i ≤ days

Visualization

Tap to expand

Understanding the Visualization

Input

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

Process

Identify busy days from meetings

Output

Count remaining free days

Key Takeaway

🎯 Key Insight: Convert overlapping intervals into non-overlapping ones, then count the gaps between them

Asked in

G Google 23 M Microsoft 18 a Amazon 15

The key insight is to handle overlapping meetings efficiently. For small days, use boolean array marking O(days). For large days, sort and merge intervals first O(n log n). Best approach depends on constraints: Sort and Merge is optimal for large days. Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Merge Intervals	O(n log n)	O(n)	Sort meetings by start time, merge overlapping intervals, then count gaps
Brute Force - Check Each Day	O(days × meetings)	O(1)	For each day from 1 to days, check if it's covered by any meeting
Boolean Array Marking	O(days + sum of meeting lengths)	O(days)	Use boolean array to mark busy days, then count unmarked days

Sort and Merge Intervals — Algorithm Steps

Sort meetings by start time
Merge overlapping intervals
Count days between merged intervals and boundaries

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Meetings

Order meetings by start time

Merge Overlaps

Combine overlapping meetings into single intervals

Count Gaps

Calculate free days between merged intervals

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    int* arr1 = (int*)a;
    int* arr2 = (int*)b;
    return arr1[0] - arr2[0];
}

int solution(int days, int meetings[][2], int meetingCount) {
    if (meetingCount == 0) {
        return days;
    }
    
    // Sort meetings by start time
    qsort(meetings, meetingCount, sizeof(int[2]), compare);
    
    // Merge overlapping intervals
    int merged[100][2];
    int mergedCount = 0;
    
    for (int i = 0; i < meetingCount; i++) {
        if (mergedCount > 0 && merged[mergedCount-1][1] >= meetings[i][0] - 1) {
            if (merged[mergedCount-1][1] < meetings[i][1]) {
                merged[mergedCount-1][1] = meetings[i][1];
            }
        } else {
            merged[mergedCount][0] = meetings[i][0];
            merged[mergedCount][1] = meetings[i][1];
            mergedCount++;
        }
    }
    
    // Count free days
    int freeDays = 0;
    
    // Days before first meeting
    if (merged[0][0] > 1) {
        freeDays += merged[0][0] - 1;
    }
    
    // Days between meetings
    for (int i = 1; i < mergedCount; i++) {
        int gap = merged[i][0] - merged[i-1][1] - 1;
        if (gap > 0) {
            freeDays += gap;
        }
    }
    
    // Days after last meeting
    if (merged[mergedCount-1][1] < days) {
        freeDays += days - merged[mergedCount-1][1];
    }
    
    return freeDays;
}

int main() {
    int days;
    scanf("%d", &days);
    
    char line[1000];
    scanf(" %s", line);
    
    int meetings[100][2];
    int meetingCount = 0;
    
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            meetings[meetingCount][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            meetings[meetingCount][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            meetingCount++;
        }
        ptr++;
    }
    
    printf("%d\n", solution(days, meetings, meetingCount));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting meetings takes O(n log n), merging takes O(n)

⚡ Linearithmic

Space Complexity

O(n)

Extra space for storing merged intervals

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Merge Intervals — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler