Employee Free Time
Mahabharata — The Soldiers' Rest — Finding the Gaps When All Warriors Are Free
यत्र सर्वे योधाः विश्रान्ताः एकसमये। तत् शान्तिकालं ज्ञात्वा नेता पुनः आयोजयेत्॥
*When all warriors rest simultaneously — that is the sacred pause. The commander identifies these gaps and plans the next deployment.*
The Story
Each soldier has their own work schedule — a list of non-overlapping intervals. We need to find the time slots when ALL soldiers are simultaneously free.
For example: - Soldier 1: [[1,3],[6,7]] - Soldier 2: [[2,4]] - Soldier 3: [[2,5],[9,12]]
We want all the free time gaps across ALL schedules combined.
Arjuna's strategy: "Flatten all schedules into a single list of intervals, sort by start time, and then find the GAPS between consecutive merged intervals."
Step 1 — Flatten: [1,3],[6,7],[2,4],[2,5],[9,12] Step 2 — Sort by start: [1,3],[2,4],[2,5],[6,7],[9,12] Step 3 — Merge (mi-1 style): - [1,3] + [2,4] → [1,4] - [1,4] + [2,5] → [1,5] - [1,5] + [6,7] → no overlap → add [1,5], start [6,7] - [6,7] + [9,12] → no overlap → add [6,7], then [9,12] Merged: [[1,5],[6,7],[9,12]]
Step 4 — Find gaps: - Between [1,5] and [6,7]: gap = [5,6] - Between [6,7] and [9,12]: gap = [7,9]
Free time: `[[5,6],[7,9]]`
Yudhishthira confirmed: "Between time 5-6 and 7-9, all soldiers are simultaneously free. We can hold a strategy meeting."
This elegantly combines mi-1's merge with a gap-detection pass.
The Captain's First Instinct
Collect all intervals, sort, merge (mi-1), then find gaps between consecutive merged intervals.
public List<Interval> employeeFreeTimeBruteForce(List<List<Interval>> schedule) {
List<int[]> all = new ArrayList<>();
for (List<Interval> emp : schedule)
for (Interval iv : emp) all.add(new int[]{iv.start, iv.end});
all.sort((a,b) -> a[0]-b[0]);
// Merge
List<int[]> merged = new ArrayList<>();
for (int[] iv : all) {
if (merged.isEmpty() || merged.get(merged.size()-1)[1] < iv[0]) merged.add(iv);
else merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1], iv[1]);
}
// Gaps
List<Interval> free = new ArrayList<>();
for (int i = 1; i < merged.size(); i++)
free.add(new Interval(merged.get(i-1)[1], merged.get(i)[0]));
return free;
}Arjuna's Flatten-Merge-Gap Wisdom
public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
List<int[]> all = new ArrayList<>();
for (List<Interval> emp : schedule)
for (Interval iv : emp) all.add(new int[]{iv.start, iv.end});
all.sort((a, b) -> a[0] - b[0]);
// Merge intervals (mi-1)
List<int[]> merged = new ArrayList<>();
for (int[] iv : all) {
if (merged.isEmpty() || merged.get(merged.size()-1)[1] < iv[0])
merged.add(new int[]{iv[0], iv[1]});
else
merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1], iv[1]);
}
// Find gaps
List<Interval> result = new ArrayList<>();
for (int i = 1; i < merged.size(); i++)
result.add(new Interval(merged.get(i-1)[1], merged.get(i)[0]));
return result;
}Step-by-Step Walkthrough
Emp1: [[1,2],[4,6]], Emp2: [[3,5]] Flatten: [1,2],[4,6],[3,5] Sort: [1,2],[3,5],[4,6] Merge: [1,2]+[3,5]→no overlap→[1,2],[3,5]+[4,6]→[3,6] Merged: [[1,2],[3,6]] Gaps: [2,3] Return [[2,3]] ✅
Deep Insight
**Why flatten and merge?** Individual schedules per employee don't directly show when ALL are free. By merging everything, we get the union of all busy times. The gaps in the union = everyone is free.
**Gap detection:** Simply iterate over consecutive merged intervals. The free time between interval[i] and interval[i+1] is [interval[i].end, interval[i+1].start].
**No gap at boundaries:** We don't report free time before the first interval or after the last one (presumably outside business hours or irrelevant).
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n log n) | O(n) | Flatten + sort + merge + gap |
| Optimal | O(n log n) | O(n) | Same — optimal approach IS the brute force approach |
Pattern Recognition
✅ Find free time across multiple schedules ✅ Flatten all intervals, sort, merge ✅ Gaps between consecutive merged intervals = free time ✅ Builds on mi-1 merge pattern **LeetCode Trigger Phrases:** → "employee free time" → "find gaps between all merged intervals" → "when are all employees free"
Bhagavad Gita 2.71
विहाय कामान्यः सर्वान्पुमांश्चरति निःस्पृहः। निर्ममो निरहंकारः स शान्तिमधिगच्छति॥
The person who has abandoned all desires and moves about without longing, without the sense of mine, without ego — that one attains peace.
Connection: Free time is the space of peace — when all obligations (intervals) have been accounted for and what remains are the sacred gaps. The algorithm doesn't search for free time directly; it finds the complete union of all commitments and then identifies what lies beyond them. Like the sage who attains peace not by seeking it but by releasing all desires, the free intervals emerge naturally from the absence of all busy ones.