Employee Free Time

🎯

Employee Free Time

hardINTERVALSFacebookAmazonGoogle

Imagine coordinating meetings for multiple employees and wanting to find common free time slots when everyone is available.

💡 This problem involves merging multiple sorted lists of intervals and then finding gaps between the merged intervals. Beginners often struggle because it requires combining interval merging with multi-list processing and careful gap detection.

📋

Problem Statement

Given a list schedule where schedule[i] is a list of non-overlapping intervals representing the working hours of the i-th employee, return the list of finite intervals representing common, positive-length free time intervals across all employees, sorted by start time.

1 ≤ number of employees ≤ 10^51 ≤ number of intervals per employee ≤ 10^5Intervals are non-overlapping within each employee's scheduleIntervals are sorted by start time within each employee's scheduleOutput intervals must have positive length

💡

Example

Input"[[[1,2],[5,6]],[[1,3]],[[4,10]]]"

Output[[3,4]]

Merging all intervals gives [1,3], [4,10], [5,6] merged into [1,3] and [4,10]. The gap between 3 and 4 is free time for all employees.

• All employees have fully overlapping schedules → output is empty list
• Only one employee → free time is complement of their intervals (if any)
• Intervals that touch but do not overlap (e.g., [1,2] and [2,3]) → no free time between
• Employees with no intervals → entire timeline is free time

⚠️

Common Mistakes

Not sorting events properly, causing incorrect free time detection

Free intervals may be reported incorrectly or missed

✅ Sort events by time, and if times tie, process end events before start events

Including zero-length intervals as free time

Output contains intervals like [2,2], which are invalid

✅ Only add free intervals where start < end

Merging intervals incorrectly by not updating end time properly

Overlapping intervals remain separate, causing wrong free time gaps

✅ When merging, update the end time to max of current and new interval

Assuming touching intervals (e.g., [1,2] and [2,3]) create free time

Incorrectly reports free time between intervals that only touch

✅ Treat touching intervals as continuous; no gap if end == start

Not handling empty schedules or employees with no intervals

Code may crash or return incorrect results

✅ Check for empty inputs and handle gracefully, possibly returning empty free time or entire timeline

🧠

Brute Force (Flatten and Check All Time Points)

💡 This approach exists to build intuition by trying all possible times and checking if all employees are free, which is conceptually simple but inefficient.

Intuition

Check every possible time point in the union of all intervals and verify if all employees are free at that time, then merge consecutive free points into intervals.

Algorithm

1. Collect all intervals from all employees into one list.
2. Find the minimum start time and maximum end time across all intervals.
3. For each time unit between min start and max end, check if it lies outside all employees' working intervals.
4. Merge consecutive free time points into intervals and return.

💡 This approach is straightforward but inefficient because it checks every time unit, which is impractical for large inputs.

</>

Code

from typing import List

def employeeFreeTime(schedule: List[List[List[int]]]) -> List[List[int]]:
    # Flatten all intervals
    intervals = []
    for emp in schedule:
        for interval in emp:
            intervals.append(interval)
    if not intervals:
        return []
    min_start = min(i[0] for i in intervals)
    max_end = max(i[1] for i in intervals)
    free_times = []
    current_start = None
    # Check every integer time point
    for t in range(min_start, max_end):
        # Check if t is free for all employees
        busy = False
        for emp in schedule:
            for interval in emp:
                if interval[0] <= t < interval[1]:
                    busy = True
                    break
            if busy:
                break
        if not busy:
            if current_start is None:
                current_start = t
        else:
            if current_start is not None:
                free_times.append([current_start, t])
                current_start = None
    if current_start is not None:
        free_times.append([current_start, max_end])
    return free_times

# Driver code
if __name__ == '__main__':
    schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
    print(employeeFreeTime(schedule))

Line Notes

intervals = []Initialize a list to hold all intervals from all employees

for emp in schedule:Iterate over each employee's schedule

min_start = min(i[0] for i in intervals)Find earliest start time among all intervals

for t in range(min_start, max_end):Check every integer time point in the global timeline

if interval[0] <= t < interval[1]:Check if current time t is within any employee's working interval

if current_start is None:Start a new free interval when a free time point is found

free_times.append([current_start, t])Close the free interval when busy time is encountered

import java.util.*;

public class EmployeeFreeTime {
    public static List<int[]> employeeFreeTime(List<List<int[]>> schedule) {
        List<int[]> intervals = new ArrayList<>();
        for (List<int[]> emp : schedule) {
            intervals.addAll(emp);
        }
        if (intervals.isEmpty()) return new ArrayList<>();
        int minStart = Integer.MAX_VALUE, maxEnd = Integer.MIN_VALUE;
        for (int[] interval : intervals) {
            minStart = Math.min(minStart, interval[0]);
            maxEnd = Math.max(maxEnd, interval[1]);
        }
        List<int[]> freeTimes = new ArrayList<>();
        Integer currentStart = null;
        for (int t = minStart; t < maxEnd; t++) {
            boolean busy = false;
            for (List<int[]> emp : schedule) {
                for (int[] interval : emp) {
                    if (interval[0] <= t && t < interval[1]) {
                        busy = true;
                        break;
                    }
                }
                if (busy) break;
            }
            if (!busy) {
                if (currentStart == null) currentStart = t;
            } else {
                if (currentStart != null) {
                    freeTimes.add(new int[]{currentStart, t});
                    currentStart = null;
                }
            }
        }
        if (currentStart != null) {
            freeTimes.add(new int[]{currentStart, maxEnd});
        }
        return freeTimes;
    }

    public static void main(String[] args) {
        List<List<int[]>> schedule = new ArrayList<>();
        schedule.add(Arrays.asList(new int[]{1,2}, new int[]{5,6}));
        schedule.add(Arrays.asList(new int[]{1,3}));
        schedule.add(Arrays.asList(new int[]{4,10}));
        List<int[]> result = employeeFreeTime(schedule);
        for (int[] interval : result) {
            System.out.println("[" + interval[0] + "," + interval[1] + "]");
        }
    }
}

Line Notes

List<int[]> intervals = new ArrayList<>();Collect all intervals from all employees into one list

int minStart = Integer.MAX_VALUEInitialize minStart to find earliest interval start

for (int t = minStart; t < maxEnd; t++) {Iterate over every time unit in the global timeline

if (interval[0] <= t && t < interval[1]) {Check if current time t is within any employee's working interval

if (currentStart == null) currentStart = t;Start a new free interval when a free time point is found

freeTimes.add(new int[]{currentStart, t});Close the free interval when busy time is encountered

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

vector<vector<int>> employeeFreeTime(vector<vector<vector<int>>>& schedule) {
    vector<vector<int>> intervals;
    for (auto& emp : schedule) {
        for (auto& interval : emp) {
            intervals.push_back(interval);
        }
    }
    if (intervals.empty()) return {};
    int minStart = INT_MAX, maxEnd = INT_MIN;
    for (auto& interval : intervals) {
        minStart = min(minStart, interval[0]);
        maxEnd = max(maxEnd, interval[1]);
    }
    vector<vector<int>> freeTimes;
    int currentStart = -1;
    for (int t = minStart; t < maxEnd; t++) {
        bool busy = false;
        for (auto& emp : schedule) {
            for (auto& interval : emp) {
                if (interval[0] <= t && t < interval[1]) {
                    busy = true;
                    break;
                }
            }
            if (busy) break;
        }
        if (!busy) {
            if (currentStart == -1) currentStart = t;
        } else {
            if (currentStart != -1) {
                freeTimes.push_back({currentStart, t});
                currentStart = -1;
            }
        }
    }
    if (currentStart != -1) {
        freeTimes.push_back({currentStart, maxEnd});
    }
    return freeTimes;
}

int main() {
    vector<vector<vector<int>>> schedule = {{{1,2},{5,6}},{{1,3}},{{4,10}}};
    vector<vector<int>> result = employeeFreeTime(schedule);
    for (auto& interval : result) {
        cout << "[" << interval[0] << "," << interval[1] << "]\n";
    }
    return 0;
}

Line Notes

vector<vector<int>> intervals;Flatten all intervals from all employees into one vector

int minStart = INT_MAX, maxEnd = INT_MIN;Initialize variables to find global start and end times

for (int t = minStart; t < maxEnd; t++) {Check every integer time point in the timeline

if (interval[0] <= t && t < interval[1]) {Determine if current time t is busy for any employee

if (currentStart == -1) currentStart = t;Mark the start of a free interval

freeTimes.push_back({currentStart, t});Add the free interval when busy time is encountered

function employeeFreeTime(schedule) {
    let intervals = [];
    for (let emp of schedule) {
        for (let interval of emp) {
            intervals.push(interval);
        }
    }
    if (intervals.length === 0) return [];
    let minStart = Math.min(...intervals.map(i => i[0]));
    let maxEnd = Math.max(...intervals.map(i => i[1]));
    let freeTimes = [];
    let currentStart = null;
    for (let t = minStart; t < maxEnd; t++) {
        let busy = false;
        for (let emp of schedule) {
            for (let interval of emp) {
                if (interval[0] <= t && t < interval[1]) {
                    busy = true;
                    break;
                }
            }
            if (busy) break;
        }
        if (!busy) {
            if (currentStart === null) currentStart = t;
        } else {
            if (currentStart !== null) {
                freeTimes.push([currentStart, t]);
                currentStart = null;
            }
        }
    }
    if (currentStart !== null) {
        freeTimes.push([currentStart, maxEnd]);
    }
    return freeTimes;
}

// Driver code
const schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]];
console.log(employeeFreeTime(schedule));

Line Notes

let intervals = [];Flatten all employee intervals into one array

let minStart = Math.min(...intervals.map(i => i[0]));Find earliest start time globally

for (let t = minStart; t < maxEnd; t++) {Iterate over every time unit in the timeline

if (interval[0] <= t && t < interval[1]) {Check if current time t is within any employee's working interval

if (currentStart === null) currentStart = t;Start a new free interval when free time is found

freeTimes.push([currentStart, t]);Close the free interval when busy time is encountered

⏱

Complexity

TimeO(N * M * T) where N is number of employees, M is average intervals per employee, T is timeline length

SpaceO(N * M) to store all intervals

We check every time unit in the global timeline against all intervals of all employees, leading to very high complexity.

💡 For example, if there are 100 employees each with 10 intervals and timeline length 1000, this approach does about 1,000,000 checks.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and correctness before optimizing.

🧠

Sorting All Intervals and Merging

💡 This approach improves efficiency by merging all intervals into a single sorted list and then finding gaps, which is a common pattern in interval problems.

Intuition

Combine all intervals from all employees, sort them by start time, merge overlapping intervals, then find gaps between merged intervals as free time.

Algorithm

1. Flatten all intervals from all employees into one list.
2. Sort the intervals by start time.
3. Iterate through sorted intervals and merge overlapping ones.
4. Between merged intervals, collect gaps as free time intervals.

💡 This approach leverages sorting and merging, which is a fundamental technique for interval problems and reduces complexity drastically.

</>

Code

from typing import List

def employeeFreeTime(schedule: List[List[List[int]]]) -> List[List[int]]:
    intervals = []
    for emp in schedule:
        intervals.extend(emp)
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    free_times = []
    for i in range(1, len(merged)):
        start = merged[i-1][1]
        end = merged[i][0]
        if start < end:
            free_times.append([start, end])
    return free_times

# Driver code
if __name__ == '__main__':
    schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
    print(employeeFreeTime(schedule))

Line Notes

intervals.extend(emp)Add all intervals from each employee into one list

intervals.sort(key=lambda x: x[0])Sort intervals by start time to prepare for merging

if not merged or merged[-1][1] < interval[0]:If no overlap, append interval to merged list

merged[-1][1] = max(merged[-1][1], interval[1])Merge overlapping intervals by extending end time

for i in range(1, len(merged))Iterate over merged intervals to find gaps

if start < end:Only add intervals with positive length as free time

import java.util.*;

public class EmployeeFreeTime {
    public static List<int[]> employeeFreeTime(List<List<int[]>> schedule) {
        List<int[]> intervals = new ArrayList<>();
        for (List<int[]> emp : schedule) {
            intervals.addAll(emp);
        }
        intervals.sort(Comparator.comparingInt(a -> a[0]));
        List<int[]> merged = new ArrayList<>();
        for (int[] interval : intervals) {
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
            }
        }
        List<int[]> freeTimes = new ArrayList<>();
        for (int i = 1; i < merged.size(); i++) {
            int start = merged.get(i - 1)[1];
            int end = merged.get(i)[0];
            if (start < end) {
                freeTimes.add(new int[]{start, end});
            }
        }
        return freeTimes;
    }

    public static void main(String[] args) {
        List<List<int[]>> schedule = new ArrayList<>();
        schedule.add(Arrays.asList(new int[]{1,2}, new int[]{5,6}));
        schedule.add(Arrays.asList(new int[]{1,3}));
        schedule.add(Arrays.asList(new int[]{4,10}));
        List<int[]> result = employeeFreeTime(schedule);
        for (int[] interval : result) {
            System.out.println("[" + interval[0] + "," + interval[1] + "]");
        }
    }
}

Line Notes

intervals.addAll(emp);Flatten all employee intervals into one list

intervals.sort(Comparator.comparingInt(a -> a[0]));Sort intervals by start time for merging

if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {If no overlap, add interval to merged list

merged.get(merged.size() - 1)[1] = Math.max(...)Extend end time to merge overlapping intervals

for (int i = 1; i < merged.size(); i++) {Find gaps between merged intervals

if (start < end) {Add only positive length intervals as free time

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> employeeFreeTime(vector<vector<vector<int>>>& schedule) {
    vector<vector<int>> intervals;
    for (auto& emp : schedule) {
        for (auto& interval : emp) {
            intervals.push_back(interval);
        }
    }
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });
    vector<vector<int>> merged;
    for (auto& interval : intervals) {
        if (merged.empty() || merged.back()[1] < interval[0]) {
            merged.push_back(interval);
        } else {
            merged.back()[1] = max(merged.back()[1], interval[1]);
        }
    }
    vector<vector<int>> freeTimes;
    for (int i = 1; i < (int)merged.size(); i++) {
        int start = merged[i-1][1];
        int end = merged[i][0];
        if (start < end) {
            freeTimes.push_back({start, end});
        }
    }
    return freeTimes;
}

int main() {
    vector<vector<vector<int>>> schedule = {{{1,2},{5,6}},{{1,3}},{{4,10}}};
    vector<vector<int>> result = employeeFreeTime(schedule);
    for (auto& interval : result) {
        cout << "[" << interval[0] << "," << interval[1] << "]\n";
    }
    return 0;
}

Line Notes

sort(intervals.begin(), intervals.end(), ...Sort all intervals by start time to prepare for merging

if (merged.empty() || merged.back()[1] < interval[0]) {Add interval if no overlap with last merged

merged.back()[1] = max(merged.back()[1], interval[1]);Merge overlapping intervals by extending end time

for (int i = 1; i < (int)merged.size(); i++) {Iterate to find gaps between merged intervals

if (start < end) {Only add intervals with positive length as free time

function employeeFreeTime(schedule) {
    let intervals = [];
    for (let emp of schedule) {
        intervals.push(...emp);
    }
    intervals.sort((a, b) => a[0] - b[0]);
    let merged = [];
    for (let interval of intervals) {
        if (merged.length === 0 || merged[merged.length - 1][1] < interval[0]) {
            merged.push(interval);
        } else {
            merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
        }
    }
    let freeTimes = [];
    for (let i = 1; i < merged.length; i++) {
        let start = merged[i - 1][1];
        let end = merged[i][0];
        if (start < end) {
            freeTimes.push([start, end]);
        }
    }
    return freeTimes;
}

// Driver code
const schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]];
console.log(employeeFreeTime(schedule));

Line Notes

intervals.push(...emp);Flatten all employee intervals into one array

intervals.sort((a, b) => a[0] - b[0]);Sort intervals by start time for merging

if (merged.length === 0 || merged[merged.length - 1][1] < interval[0]) {Add interval if no overlap with last merged

merged[merged.length - 1][1] = Math.max(...)Merge overlapping intervals by extending end time

for (let i = 1; i < merged.length; i++) {Find gaps between merged intervals

if (start < end) {Add only positive length intervals as free time

⏱

Complexity

TimeO(N log N) where N is total number of intervals

SpaceO(N) for storing intervals and merged list

Sorting all intervals dominates time complexity; merging and gap finding are linear.

💡 For 10,000 intervals, sorting takes about 10,000 * log2(10,000) ≈ 132,877 operations, which is efficient.

Interview Verdict: Accepted

This approach is efficient and practical for large inputs and is a common interview solution.

🧠

Sweep Line / Event Processing

💡 This approach uses a sweep line technique to process interval start and end events, tracking how many employees are busy at each point, allowing direct detection of free intervals.

Intuition

Convert intervals into start and end events, sort them, then sweep through the timeline counting active intervals. When count drops to zero, it means all employees are free.

Algorithm

1. Create a list of all start and end events from all intervals, marking start as +1 and end as -1.
2. Sort all events by time; if times are equal, end events come before start events.
3. Initialize a counter to track active intervals and a variable to track previous event time.
4. Sweep through events, updating the counter; when counter is zero, record the gap between previous event and current event as free time.

💡 This approach efficiently tracks overlapping intervals without merging, directly identifying free gaps by counting active intervals.

</>

Code

from typing import List

def employeeFreeTime(schedule: List[List[List[int]]]) -> List[List[int]]:
    events = []
    for emp in schedule:
        for interval in emp:
            events.append((interval[0], 1))  # start event
            events.append((interval[1], -1)) # end event
    # Sort by time; end events before start if tie
    events.sort(key=lambda x: (x[0], x[1]))
    free_times = []
    active = 0
    prev = None
    for time, e_type in events:
        if active == 0 and prev is not None and prev < time:
            free_times.append([prev, time])
        active += e_type
        prev = time
    return free_times

# Driver code
if __name__ == '__main__':
    schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
    print(employeeFreeTime(schedule))

Line Notes

events = []Initialize list to hold all start and end events

events.append((interval[0], 1))Add start event with +1 to indicate interval begins

events.append((interval[1], -1))Add end event with -1 to indicate interval ends

events.sort(key=lambda x: (x[0], x[1]))Sort events by time; end events before start if times equal to avoid false free time

if active == 0 and prev is not None and prev < time:When no active intervals, record free time between prev and current event

active += e_typeUpdate active interval count based on event type

prev = timeUpdate previous event time for next iteration

import java.util.*;

public class EmployeeFreeTime {
    public static List<int[]> employeeFreeTime(List<List<int[]>> schedule) {
        List<int[]> events = new ArrayList<>();
        for (List<int[]> emp : schedule) {
            for (int[] interval : emp) {
                events.add(new int[]{interval[0], 1}); // start event
                events.add(new int[]{interval[1], -1}); // end event
            }
        }
        events.sort((a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            return a[1] - b[1]; // end event (-1) before start event (1)
        });
        List<int[]> freeTimes = new ArrayList<>();
        int active = 0;
        Integer prev = null;
        for (int[] event : events) {
            int time = event[0], type = event[1];
            if (active == 0 && prev != null && prev < time) {
                freeTimes.add(new int[]{prev, time});
            }
            active += type;
            prev = time;
        }
        return freeTimes;
    }

    public static void main(String[] args) {
        List<List<int[]>> schedule = new ArrayList<>();
        schedule.add(Arrays.asList(new int[]{1,2}, new int[]{5,6}));
        schedule.add(Arrays.asList(new int[]{1,3}));
        schedule.add(Arrays.asList(new int[]{4,10}));
        List<int[]> result = employeeFreeTime(schedule);
        for (int[] interval : result) {
            System.out.println("[" + interval[0] + "," + interval[1] + "]");
        }
    }
}

Line Notes

List<int[]> events = new ArrayList<>();Collect all start and end events from intervals

events.add(new int[]{interval[0], 1});Add start event with +1 to indicate interval begins

events.add(new int[]{interval[1], -1});Add end event with -1 to indicate interval ends

events.sort((a, b) -> { ... });Sort events by time; end events before start if tie to avoid false free time

if (active == 0 && prev != null && prev < time) {Record free time when no active intervals between prev and current event

active += type;Update count of active intervals based on event type

prev = time;Update previous event time for next iteration

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> employeeFreeTime(vector<vector<vector<int>>>& schedule) {
    vector<pair<int,int>> events;
    for (auto& emp : schedule) {
        for (auto& interval : emp) {
            events.emplace_back(interval[0], 1); // start event
            events.emplace_back(interval[1], -1); // end event
        }
    }
    sort(events.begin(), events.end(), [](const pair<int,int>& a, const pair<int,int>& b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second < b.second; // end event (-1) before start event (1)
    });
    vector<vector<int>> freeTimes;
    int active = 0;
    int prev = -1;
    bool first = true;
    for (auto& e : events) {
        int time = e.first, type = e.second;
        if (active == 0 && !first && prev < time) {
            freeTimes.push_back({prev, time});
        }
        active += type;
        prev = time;
        first = false;
    }
    return freeTimes;
}

int main() {
    vector<vector<vector<int>>> schedule = {{{1,2},{5,6}},{{1,3}},{{4,10}}};
    vector<vector<int>> result = employeeFreeTime(schedule);
    for (auto& interval : result) {
        cout << "[" << interval[0] << "," << interval[1] << "]\n";
    }
    return 0;
}

Line Notes

events.emplace_back(interval[0], 1);Add start event with +1 to indicate interval begins

events.emplace_back(interval[1], -1);Add end event with -1 to indicate interval ends

sort(events.begin(), events.end(), ...Sort events by time; end events before start if tie to avoid false free time

if (active == 0 && !first && prev < time) {Record free time when no active intervals between prev and current event

active += type;Update count of active intervals based on event type

prev = time;Update previous event time for next iteration

function employeeFreeTime(schedule) {
    let events = [];
    for (let emp of schedule) {
        for (let interval of emp) {
            events.push([interval[0], 1]); // start event
            events.push([interval[1], -1]); // end event
        }
    }
    events.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
    let freeTimes = [];
    let active = 0;
    let prev = null;
    for (let [time, type] of events) {
        if (active === 0 && prev !== null && prev < time) {
            freeTimes.push([prev, time]);
        }
        active += type;
        prev = time;
    }
    return freeTimes;
}

// Driver code
const schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]];
console.log(employeeFreeTime(schedule));

Line Notes

events.push([interval[0], 1]);Add start event with +1 to indicate interval begins

events.push([interval[1], -1]);Add end event with -1 to indicate interval ends

events.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);Sort events by time; end events before start if tie to avoid false free time

if (active === 0 && prev !== null && prev < time) {Record free time when no active intervals between prev and current event

active += type;Update count of active intervals based on event type

prev = time;Update previous event time for next iteration

⏱

Complexity

TimeO(N log N) where N is total number of interval endpoints

SpaceO(N) for storing events and output

Sorting all 2N events dominates time; sweeping through events is linear.

💡 For 10,000 intervals, we have 20,000 events; sorting takes about 20,000 * log2(20,000) ≈ 280,000 operations, efficient for interviews.

Interview Verdict: Accepted

This is the optimal and most elegant approach, often preferred in interviews for interval union and gap problems.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, approach 3 (Sweep Line) is preferred for its clarity and efficiency; approach 2 is a good fallback; approach 1 is only for initial explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(N * M * T) (very large)	O(N * M)	No	N/A	Mention only - never code due to inefficiency
2. Sorting and Merging	O(N log N)	O(N)	No	Yes	Good to code if sweep line is not known
3. Sweep Line / Event Processing	O(N log N)	O(N)	No	Yes	Optimal approach to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding each approach, and learn how to explain your thought process clearly in interviews.

How to Present

Step 1: Clarify the problem and ask about input format and constraints.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the sorting and merging approach to improve efficiency.Step 4: Present the sweep line technique as the optimal solution.Step 5: Code the chosen approach carefully, then test with examples and edge cases.

Time Allocation

Clarify: 3min → Approach discussion: 7min → Code: 10min → Testing & edge cases: 5min. Total ~25min

What the Interviewer Tests

Interviewer tests your ability to handle multiple sorted lists, merge intervals correctly, and find gaps efficiently. They also assess your understanding of event processing and edge cases.

Common Follow-ups

• How to handle infinite free time before first interval or after last interval? → Usually ignored or clarified by interviewer.
• What if intervals are not sorted within each employee? → Sort them first or clarify input assumptions.

💡 Follow-ups test your ability to handle input variations and boundary conditions, common in real interviews.

🔍

Pattern Recognition

When to Use

1) Multiple sorted interval lists, 2) Need to find common free gaps, 3) Intervals may overlap, 4) Output sorted intervals

Signature Phrases

common free timeemployee schedulesnon-overlapping intervals

NOT This Pattern When

Problems that require interval partitioning or maximum overlap count without gap detection

Similar Problems

Merge Intervals - merging overlapping intervalsMeeting Rooms II - counting rooms neededInsert Interval - inserting and merging intervals

Practice

1. Consider the following Python code implementing the optimal car pooling solution. What is the return value when called with trips = [[2,1,5],[3,3,7]] and capacity = 4?

def carPooling(trips, capacity):
    max_location = 0
    for _, start, end in trips:
        max_location = max(max_location, end)
    diff = [0] * (max_location + 1)
    for num, start, end in trips:
        diff[start] += num
        diff[end] -= num
    current_passengers = 0
    for i in range(max_location + 1):
        current_passengers += diff[i]
        if current_passengers > capacity:
            return false
    return true

print(carPooling([[2,1,5],[3,3,7]], 4))

easy

A. Error due to index out of range

B. true

C. false

D. true only if capacity is at least 5

Solution

1. Step 1: Build difference array

   diff after processing trips: diff[1]+=2, diff[5]-=2, diff[3]+=3, diff[7]-=3

2. Step 2: Sweep through diff to track passengers

   At location 1: current_passengers=2; at 3: current_passengers=5 (2+3), which exceeds capacity=4 -> return false

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Passenger count exceeds capacity at location 3 [OK]

Hint: Sum diffs to track passengers, check capacity [OK]

Common Mistakes:

• Off-by-one in diff array indexing
• Checking capacity only at trip start
• Forgetting to decrement at trip end

2. You are given a list of non-overlapping intervals sorted by their start times, and a new interval to insert. Which approach guarantees an optimal solution that correctly merges overlapping intervals after insertion?

easy

A. Use a greedy approach that inserts the new interval at the end and merges overlapping intervals in one pass without sorting.

B. Iterate through intervals and insert the new interval in the correct position without sorting, then merge overlapping intervals.

C. Use dynamic programming to find the minimal set of merged intervals after insertion.

D. Append the new interval, sort all intervals by start time, then merge overlapping intervals in one pass.

Solution

1. Step 1: Understand the problem constraints

   The intervals are sorted and non-overlapping initially, but inserting a new interval may cause overlaps.

2. Step 2: Identify the approach that guarantees correct merging

   Appending and then sorting ensures the new interval is placed correctly relative to others, allowing a single pass merge to handle all overlaps reliably.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting after insertion ensures correct order for merging [OK]

Hint: Sort after insertion to guarantee correct merge order [OK]

Common Mistakes:

• Assuming intervals remain sorted after insertion without sorting
• Trying to merge without sorting leads to missed overlaps
• Using DP unnecessarily complicates the problem

3. Given a list of train arrival and departure times, you need to find the minimum number of platforms required so that no train waits. Which approach guarantees an optimal solution for this problem?

easy

A. Use a greedy algorithm that assigns platforms as trains arrive without sorting times.

B. Use a sweep line algorithm by creating events for arrivals and departures, sorting them, and tracking concurrent trains.

C. Use dynamic programming to find the maximum overlap of intervals by building a state table.

D. Use nested loops to check every pair of trains for overlap and count maximum overlaps.

Solution

1. Step 1: Understand the problem requires tracking concurrent trains

   The key is to find the maximum number of trains present at the station simultaneously.

2. Step 2: Recognize that sorting events and sweeping through them tracks concurrency efficiently

   By creating arrival and departure events and sorting them, we can increment or decrement the count of trains present, capturing the peak count.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sweep line tracks concurrency optimally [OK]

Hint: Sort events and sweep to track concurrency [OK]

Common Mistakes:

• Assuming greedy assignment without sorting works
• Trying DP which is unnecessary overhead
• Using nested loops which is inefficient

4. What is the time complexity of the optimal car pooling solution using the difference array and prefix sum approach, given n trips and maximum location L?

medium

A. O(n * L) because we must simulate passenger count at every location for each trip

B. O(n + L) because we process each trip once and then sweep through the difference array once

C. O(n log n) due to sorting trips by start location before processing

D. O(L) because the difference array size dominates and trips are processed in constant time

Solution

1. Step 1: Analyze trip processing

   Each of the n trips updates two positions in the difference array -> O(n)

2. Step 2: Analyze prefix sum sweep

   We iterate over the difference array of size L once -> O(L)

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum of O(n) + O(L) operations [OK]

Hint: Difference array updates O(n), prefix sum O(L) [OK]

Common Mistakes:

• Confusing brute force O(n*L) with optimal
• Assuming sorting is required
• Ignoring prefix sum sweep cost

5. Consider this buggy code snippet for removing covered intervals:

def remove_covered_intervals(intervals):
    intervals.sort(key=lambda x: (x[0], x[1]))  # Bug here
    count = 0
    max_end = 0
    for _, end in intervals:
        if end > max_end:
            count += 1
            max_end = end
    return count

What is the bug in this code?

medium

A. The condition 'if end > max_end' should be 'if end >= max_end' to include equal ends.

B. max_end is not updated correctly inside the loop.

C. Sorting by end ascending instead of descending causes coverage detection failure.

D. The nested loop for coverage check is missing, causing incorrect results.

Solution

1. Step 1: Analyze sorting key

   Sorting by (start ascending, end ascending) orders intervals with same start from shortest to longest, which breaks coverage detection.

2. Step 2: Understand coverage detection logic

   Coverage detection relies on intervals with same start being sorted longest first (end descending) so covered intervals come after.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting end ascending causes missed coverage when starts equal [OK]

Hint: Sort end descending to detect coverage correctly [OK]

Common Mistakes:

• Sorting end ascending instead of descending
• Using strict inequality incorrectly