#759 Employee Free Time
the problem
In plain words
schedule.get(i) is employee i's list of working intervals [start, end]; each list is sorted and its intervals don't overlap. Return, in sorted order, every finite stretch of positive length when no employee is working. Intervals are Interval objects with public start and end fields. Touching intervals such as [1,2] and [2,3] leave no free time between them.
in schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
out [[3,4]]
Someone is busy over [1,3] and over [4,10]. The time before 1 and after 10 is endless, so it doesn't count.
in schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
out [[5,6],[7,9]]
- 1 ≤ schedule.length, schedule[i].length ≤ 50
- 0 ≤ start < end ≤ 10⁸
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code right here. Stuck for 20 minutes? Open one hint at a time.
This one is LeetCode Premium. You don't need a subscription: solve it right here. The free alternative linked above is the closest free practice; its label says how close it is.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternInterval merging (sort by start)K-way merge
Who is busy doesn't matter, only whether anyone is. Merge all the busy intervals into blocks; the gaps between consecutive blocks are the common free time.
solutions
From brute force to optimal
Free time can only start and end at some interval's start or end. Check each stretch between consecutive points against everyone.
- Collect every start and end in a TreeSet.
- For each pair of neighbouring points (p, q): if no interval overlaps (p, q), it's free.
- Return the free stretches in order.
Up to 2N points, and each check scans all N intervals.
The set of points.
class Solution { public List<Interval> employeeFreeTime(List<List<Interval>> schedule) { TreeSet<Integer> points = new TreeSet<>(); // every start and end, sorted, no repeats for (List<Interval> person : schedule) { for (Interval iv : person) { points.add(iv.start); points.add(iv.end); } } List<Interval> free = new ArrayList<>(); Integer prev = null; for (int p : points) { if (prev != null && !anyoneBusy(schedule, prev, p)) free.add(new Interval(prev, p)); prev = p; } return free; } /** Does some interval overlap the open gap (from, to)? Scans everyone: O(N). */ private boolean anyoneBusy(List<List<Interval>> schedule, int from, int to) { for (List<Interval> person : schedule) { for (Interval iv : person) { if (iv.start < to && from < iv.end) return true; } } return false; }}Put every interval in one list, sort by start, and keep the latest end seen. A start beyond that end opens a gap.
- Flatten all lists and sort by start.
- end = first interval's end.
- For each interval: if start > end, add [end, start]; end = max(end, interval end).
Sorting all N intervals dominates.
The flattened list.
class Solution { public List<Interval> employeeFreeTime(List<List<Interval>> schedule) { List<Interval> all = new ArrayList<>(); for (List<Interval> person : schedule) all.addAll(person); // who works doesn't matter all.sort((a, b) -> Integer.compare(a.start, b.start)); List<Interval> free = new ArrayList<>(); int end = all.get(0).end; // somebody is busy until `end` for (Interval iv : all) { if (iv.start > end) free.add(new Interval(end, iv.start)); // nobody works in between end = Math.max(end, iv.end); } return free; }}Each employee's list is already sorted. A min-heap holding every employee's next interval yields all intervals in start order without a full sort.
- Push each employee's first interval as (start, employee, index).
- Poll the smallest; if its start > end, add [end, start]; end = max(end, its end).
- Push that employee's next interval, if any.
N polls and pushes on a heap of size k (k = number of employees).
One heap entry per employee (plus the output).
class Solution { public List<Interval> employeeFreeTime(List<List<Interval>> schedule) { // {start, person, index}: one entry per person, like merging k sorted lists PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); for (int p = 0; p < schedule.size(); p++) heap.offer(new int[] {schedule.get(p).get(0).start, p, 0}); List<Interval> free = new ArrayList<>(); int end = heap.peek()[0]; // earliest start of anyone while (!heap.isEmpty()) { int[] top = heap.poll(); List<Interval> person = schedule.get(top[1]); Interval iv = person.get(top[2]); if (iv.start > end) free.add(new Interval(end, iv.start)); // a gap nobody covers end = Math.max(end, iv.end); if (top[2] + 1 < person.size()) { // that person's next interval heap.offer(new int[] {person.get(top[2] + 1).start, top[1], top[2] + 1}); } } return free; }}in the room
How to say it in the interview
talk track
- Restate: "common free time = gaps in the union of everyone's busy time."
- Give the flatten + sort + sweep version first: O(N log N).
- Then improve: each list is already sorted, so merge k sorted lists with a heap, O(N log k), just like Merge k Sorted Lists.
traps
- Reporting the endless stretch before the first interval or after the last one.
- Reporting zero-length gaps when one block ends exactly where the next starts. Use
start > end, not>=. - Setting
end = interval.endinstead of the max. A long shift can cover several later short ones.
what they ask next
Follow-ups
Only free slots of at least 30 minutes?
Filter the gaps: keep those with end − start ≥ 30.
Times when at least k of the n employees are free?
Sweep +1/−1 events in order and report the stretches where the busy count is at most n − k.
before you submit
Edge cases to test
- One employee with one interval → no free time.
- Blocks that only touch ([1,2] and [2,3]) → no free time.
- A long shift that covers other people's short shifts → no gap inside it.
practise next
Similar problems
- #56Merge IntervalsMediumin Intervals
- #23Merge k Sorted ListsHardin Heaps
- #253Meeting Rooms IIMediumin IntervalsLeetCode Premium