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. You need to continuously receive numbers from a stream and efficiently find the median after each insertion. Which approach guarantees an optimal solution with O(log n) insertion and O(1) median retrieval?

easy

A. Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half, balancing their sizes.

B. Sort the entire list after each insertion and pick the middle element(s).

C. Use a balanced binary search tree to insert and find median in O(log n) time.

D. Use a single min-heap to store all elements and extract median by popping half the elements.

Solution

1. Step 1: Understand the problem constraints

   The problem requires efficient insertion and median retrieval from a data stream.

2. Step 2: Evaluate approaches

   Sorting after each insertion is O(n log n), too slow. A balanced BST can do insertions in O(log n) but median retrieval is not O(1). Using a single min-heap cannot separate lower and upper halves, so median calculation is incorrect. Maintaining two heaps (max-heap for lower half, min-heap for upper half) allows O(log n) insertion and O(1) median retrieval by balancing sizes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two heaps balance halves for median -> [OK]

Hint: Two heaps balance halves for median retrieval [OK]

Common Mistakes:

• Sorting entire list each time is too slow
• Using one heap cannot separate halves
• Assuming balanced BST gives O(1) median retrieval

2. You are given an array of integers where you can perform operations to minimize the difference between the maximum and minimum elements. The operations allowed are doubling odd numbers once and halving even numbers multiple times. Which algorithmic approach guarantees finding the minimum possible deviation efficiently?

easy

A. Using a max-heap to iteratively reduce the maximum element while tracking the minimum

B. Brute force recursion trying all combinations of doubling and halving

C. Sorting the array and using a sliding window to find the minimal range

D. Dynamic programming to store states of all possible values after operations

Solution

1. Step 1: Understand problem constraints and operations

   The problem allows doubling odd numbers once and halving even numbers multiple times to minimize deviation.

2. Step 2: Identify approach that efficiently tracks max and min values

   Using a max-heap allows quick access to the current maximum, which can be reduced by halving, while tracking the minimum seen so far.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max-heap approach efficiently updates max and min values [OK]

Hint: Max-heap efficiently tracks max element for reduction [OK]

Common Mistakes:

• Thinking sorting + two pointers always works despite operations changing values
• Assuming brute force is feasible for large inputs
• Believing DP is needed despite no overlapping subproblems

3. Given the following Python code implementing the optimal two heaps approach for finding next intervals, what is the final returned result for the input intervals = [(2,3), (3,4), (1,2)]?

easy

A. [2, 0, 1]

B. [0, -1, 1]

C. [-1, -1, -1]

D. [1, -1, 0]

Solution

1. Step 1: Initialize heaps and result

   max_start_heap = [(-3,1), (-2,0), (-1,2)], max_end_heap = [(-4,1), (-3,0), (-2,2)], result = [-1, -1, -1]

2. Step 2: Process max_end_heap

   Pop (-4,1): max_start_heap top is -3 < 4, continue no update.
   Pop (-3,0): max_start_heap top -3 >= 3, pop candidates with start >= 3: (-3,1). min_start= -3, min_idx=1, result[0]=1.
   Push back unused candidates (none).
   Pop (-2,2): max_start_heap top -2 >= 2, pop candidates (-2,0), (-1,2). min_start= -1, min_idx=2, result[2]=2.
   Push back (-2,0).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches expected output for given input [OK]

Hint: Track heap pops carefully to find correct indices [OK]

Common Mistakes:

• Off-by-one in indices
• Not pushing back unused intervals
• Confusing start and end heaps

4. Identify the bug in the following code snippet for adding a number to the MedianFinder class that uses two heaps:

medium

A. Incorrect comparison operator in if condition.

B. Not pushing negative num into low heap (max-heap) correctly.

C. Missing balancing heaps after insertion, causing size imbalance.

D. Not updating delayed dictionary for lazy removal.

Solution

1. Step 1: Check heap insertion logic

   Numbers are pushed correctly into low (max-heap) and high (min-heap) with sign inversion for low.

2. Step 2: Identify missing balancing

   After insertion, heaps must be balanced to ensure size difference ≤ 1. Missing balancing causes incorrect median calculation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Without balancing, median calculation breaks -> [OK]

Hint: Always balance heaps after insertion to maintain median correctness [OK]

Common Mistakes:

• Forgetting to balance heaps after insertion
• Incorrect sign usage for max-heap
• Ignoring delayed removals in lazy deletion

5. Examine the following Python code snippet implementing the balanced two heaps approach for sliding window median. Which line contains a subtle bug that can cause incorrect median calculation for even window sizes?

medium

A. Line adding out_num to delayed dictionary

B. Line calculating median for even k: median = (-small[0][0] + large[0][0]) / 2

C. Line pruning heaps using delayed dictionary

D. Line with heapq.heappush(large, (-val, idx)) in balance()

Solution

1. Step 1: Analyze balance() function

   When moving elements between heaps, signs must be handled carefully to maintain max-heap and min-heap properties.

2. Step 2: Identify incorrect sign usage

   In line pushing to large heap, negation is incorrect; it should push positive val to min-heap, not negative.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Incorrect sign breaks heap order, causing wrong median [OK]

Hint: Check sign handling when moving elements between heaps [OK]

Common Mistakes:

• Incorrect sign negation when balancing heaps
• Forgetting to prune delayed elements
• Wrong median calculation for even k