Katkat
Back

Design an Employee Coverage Timeline

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This problem tests your ability to handle overlapping intervals and state tracking using a sweep-line algorithm combined with a mapping structure.

Problem Statement

You are given a list of employee shifts, where each shift contains an employee_id, name, start_time, and end_time. Multiple employees might be working simultaneously. Your task is to generate a 'coverage timeline' that describes the staffing status over time.

The output should be a list of non-overlapping intervals [start, end] representing contiguous periods of time, along with the set of employees working during that period. If no one is working, the interval should represent a 'break'.

Function Signature

def get_coverage_timeline(shifts: List[Dict]) -> List[Dict]

Input Format

  • shifts: A list of dictionaries, e.g., {'id': 1, 'name': 'Alice', 'start': 10, 'end': 20}.

Output Format

  • A list of dictionaries, each containing start, end, and a list of {'id', 'name'} pairs representing the active employees.

Example

Input:

[
  {'id': 1, 'name': 'Alice', 'start': 0, 'end': 10},
  {'id': 2, 'name': 'Bob', 'start': 5, 'end': 15}
]

Output:

[
  {'start': 0, 'end': 5, 'employees': [{'id': 1, 'name': 'Alice'}]},
  {'start': 5, 'end': 10, 'employees': [{'id': 1, 'name': 'Alice'}, {'id': 2, 'name': 'Bob'}]},
  {'start': 10, 'end': 15, 'employees': [{'id': 2, 'name': 'Bob'}]}
]

Constraints

  • 0 <= start < end.
  • The number of shifts n is up to 10,000.
  • Time values are non-negative integers.

Edge Cases

  • Shifts that are perfectly contiguous (e.g., end at 10, start at 10).
  • One shift completely contained within another.
  • No shifts provided.

Hints

Hint 1

Collect all start and end times into a sorted list of unique points to define the boundaries of the intervals.

Hint 2

For each interval between two consecutive points, identify which employees have a start time = current_end.

Hint 3

Use a sweep-line approach to process event points (start/end) and maintain a set of currently active employees.

Follow-up questions

  • How would you optimize the solution if you only needed to return the count of employees rather than their specific identities?
  • What changes are needed if the intervals must be merged when the set of active employees remains identical across consecutive segments?
  • How would you handle a scenario where 'name' changes for the same 'id' halfway through a shift?