Bird
Raised Fist0
Interview PrepintervalshardFacebookAmazonGoogle

Employee Free Time

Choose your preparation mode4 modes available
▶
Steps
setup

Collect start and end events

We iterate over each employee's schedule and extract start and end times as events, marking starts with +1 and ends with -1.

💡 Separating intervals into start and end events allows us to process all interval boundaries uniformly.
Line:for emp in schedule: for interval in emp: events.append((interval[0], 1)) # start event events.append((interval[1], -1)) # end event
💡 This step transforms nested intervals into a flat list of events, preparing for sorting and sweeping.
📊
Employee Free Time - Watch the Algorithm Execute, Step by Step
Watching each event processed and how the active interval count changes reveals exactly when free time intervals appear, making the logic crystal clear.
Step 1/12
·Active fill★Answer cell
record
(1,1)
0
(2,-1)
1
(5,1)
2
(6,-1)
3
(1,1)
4
(3,-1)
5
(4,1)
6
(10,-1)
7
Result: []
record
(1,1)
0
(1,1)
1
(2,-1)
2
(3,-1)
3
(4,1)
4
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: []
record
(1,1)
0
(1,1)
1
(2,-1)
2
(3,-1)
3
(4,1)
4
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: []
move_right
i
(1,1)
0
(1,1)
1
(2,-1)
2
(3,-1)
3
(4,1)
4
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: []
move_right
(1,1)
0
i
(1,1)
1
(2,-1)
2
(3,-1)
3
(4,1)
4
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: []
move_right
(1,1)
0
(1,1)
1
i
(2,-1)
2
(3,-1)
3
(4,1)
4
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: []
move_right
(1,1)
0
(1,1)
1
(2,-1)
2
i
(3,-1)
3
(4,1)
4
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: []
record
(1,1)
0
(1,1)
1
(2,-1)
2
(3,-1)
3
i
(4,1)
4
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: [[3,4]]
move_right
(1,1)
0
(1,1)
1
(2,-1)
2
(3,-1)
3
(4,1)
4
i
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: [[3,4]]
move_right
(1,1)
0
(1,1)
1
(2,-1)
2
(3,-1)
3
(4,1)
4
(5,1)
5
i
(6,-1)
6
(10,-1)
7
Result: [[3,4]]
move_right
(1,1)
0
(1,1)
1
(2,-1)
2
(3,-1)
3
(4,1)
4
(5,1)
5
(6,-1)
6
i
(10,-1)
7
Result: [[3,4]]
record
(1,1)
0
(1,1)
1
(2,-1)
2
(3,-1)
3
(4,1)
4
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: [[3,4]]

Key Takeaways

✓ Transforming intervals into start and end events allows a uniform sweep line approach.

This insight is hard to see from code alone because the flattening and sorting steps are subtle but crucial.

✓ Sorting events with end events before start events at the same time prevents counting intervals as active prematurely.

This ordering detail is easy to overlook but essential for correct active interval tracking.

✓ When the active count drops to zero, the gap between previous and current event times is free time.

Watching the active count change step-by-step reveals exactly when free time intervals appear.

Practice

(1/5)
1. Given two lists of closed intervals, each sorted and non-overlapping within themselves, you need to find all intervals where the two lists overlap. Which approach guarantees an optimal time complexity solution?
easy
A. Use a brute force nested loop to compare every interval in the first list with every interval in the second list.
B. Use two pointers to traverse both lists simultaneously, advancing the pointer with the smaller interval endpoint to find intersections efficiently.
C. Sort all intervals from both lists together and then merge overlapping intervals to find intersections.
D. Use dynamic programming to store and compute overlapping intervals between the two lists.

Solution

  1. Step 1: Understand problem constraints

    Both lists are sorted and non-overlapping internally, so a linear scan is possible.
  2. Step 2: Identify the optimal approach

    Two pointers allow simultaneous traversal, comparing intervals in O(m + n) time, advancing pointers based on interval endpoints.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Two pointers avoid unnecessary comparisons and achieve linear time [OK]
Hint: Two pointers exploit sorted order for linear time [OK]
Common Mistakes:
  • Assuming brute force is acceptable
  • Thinking sorting combined lists is needed
  • Misapplying DP to interval intersection
2. You are given a list of intervals and need to remove all intervals that are covered by another interval. Which approach guarantees an optimal solution with O(n log n) time complexity and O(1) extra space besides the input?
easy
A. Use a brute force nested loop to check coverage between every pair of intervals.
B. Sort intervals by start ascending and end descending, then scan once to count uncovered intervals.
C. Use dynamic programming to find the maximum set of non-covered intervals.
D. Sort intervals by end ascending and greedily pick intervals that do not overlap.

Solution

  1. Step 1: Understand sorting criteria

    Sorting intervals by start ascending and end descending ensures intervals with the same start are ordered from longest to shortest, so coverage can be detected in one pass.
  2. Step 2: Single pass coverage check

    By scanning intervals in sorted order and tracking the maximum end seen, we can count intervals that are not covered by any previous interval.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Sorting by start ascending and end descending enables O(n log n) sorting plus O(n) scanning [OK]
Hint: Sort by start asc, end desc, then scan once [OK]
Common Mistakes:
  • Sorting only by start ascending misses coverage when starts equal
  • Using nested loops causes TLE on large inputs
3. The following code attempts to count intervals containing each point using a line sweep. Identify the bug that causes incorrect counts for points exactly at interval ends.
medium
A. Line adding interval end event should use end + 1 instead of end.
B. Sorting key should sort points before interval starts.
C. Active count should be incremented after processing points, not before.
D. Result array initialization size is incorrect.

Solution

  1. Step 1: Identify event creation for interval ends

    Interval end events use 'end' instead of 'end + 1', so points exactly at interval end are processed after the interval ends.
  2. Step 2: Understand effect on counting

    Because end events are processed at 'end', points at 'end' see active count after decrement, missing that interval.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Changing to end + 1 fixes counting for points at interval ends [OK]
Hint: Interval end event must be at end+1 to include points at end [OK]
Common Mistakes:
  • Using end instead of end+1
  • Misordering events
  • Incorrect active count update
4. The following code attempts to determine if a person can attend all meetings. Identify the line containing the subtle bug that causes incorrect results for intervals that just touch (e.g., [1,5] and [5,10]).
from typing import List

def can_attend_meetings(intervals: List[List[int]]) -> bool:
    intervals.sort(key=lambda x: x[0])
    end = float('-inf')
    for interval in intervals:
        if interval[0] <= end:
            return False
        end = interval[1]
    return True
medium
A. Line 6: if interval[0] <= end:
B. Line 3: intervals.sort(key=lambda x: x[0])
C. Line 5: for interval in intervals:
D. Line 7: end = interval[1]

Solution

  1. Step 1: Understand the overlap condition

    Meetings that just touch (e.g., end=5 and start=5) should not be considered overlapping.
  2. Step 2: Identify the bug

    The condition uses <= which incorrectly treats touching intervals as overlapping. It should use < instead.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Changing <= to < fixes false positives on touching intervals [OK]
Hint: Overlap check must use <, not <= [OK]
Common Mistakes:
  • Using <= causes false overlap detection on touching intervals
5. What is the time complexity of the sweep line algorithm for finding the minimum number of platforms required given n trains, and why?
medium
A. O(n log n) due to sorting arrivals and departures separately and merging them.
B. O(n^2) because each event is compared with all others to count overlaps.
C. O(n) because we only iterate through arrivals and departures once.
D. O(n log n) because events are sorted and then processed in a single pass.

Solution

  1. Step 1: Identify sorting as the main cost

    We create 2n events and sort them by time, which takes O(n log n).
  2. Step 2: Single pass processing after sorting

    After sorting, we iterate through events once, O(n), updating counts.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Sorting dominates, linear sweep after [OK]
Hint: Sorting events dominates time complexity [OK]
Common Mistakes:
  • Assuming O(n) because of single pass ignoring sorting
  • Confusing nested loops brute force with sweep line
  • Thinking sorting arrivals and departures separately is enough
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard