Katkat
Back

Merge overlapping intervals per group in pandas

WaymoData Scientist · Onsite
EasyData ScientistOnsiteData Manipulation (SQL/Python)

Last updated

This problem tests your ability to handle temporal data by merging overlapping time intervals within distinct groups using pandas and custom logic.

Problem Statement

You are given a pandas DataFrame df representing task logs for different employees. Each row contains an employee_id, start_time, and end_time. Due to logging errors, some tasks for the same employee overlap or are contiguous.

Your task is to write a function merge_employee_tasks(df) that returns a new DataFrame where all overlapping or adjacent intervals for each employee_id are merged into single, continuous blocks. Two intervals are considered adjacent if the end_time of one equals the start_time of another.

Input Format

  • df: A DataFrame with columns ['employee_id', 'start_time', 'end_time']. Times are datetime objects.

Output Format

  • A DataFrame with the same columns, representing the merged intervals, sorted by employee_id and start_time.

Constraints

  • 1 <= len(df) <= 10^5
  • start_time is always <= end_time.

Example

# Input
   employee_id          start_time            end_time
0            1 2023-01-01 08:00:00 2023-01-01 10:00:00
1            1 2023-01-01 09:00:00 2023-01-01 11:00:00
2            1 2023-01-01 12:00:00 2023-01-01 13:00:00
3            2 2023-01-01 08:00:00 2023-01-01 09:00:00

# Output
   employee_id          start_time            end_time
0            1 2023-01-01 08:00:00 2023-01-01 11:00:00
1            1 2023-01-01 12:00:00 2023-01-01 13:00:00
2            2 2023-01-01 08:00:00 2023-01-01 09:00:00

Considerations

  • Ensure the output is sorted.
  • Handle empty DataFrames gracefully.
  • Consider the complexity of the grouping and merging logic.

Hints

Hint 1

Sort the entire DataFrame by `employee_id` and `start_time` first to simplify the comparison logic.

Hint 2

For each group, iterate through the sorted intervals and maintain a 'current' interval that extends as long as the next start time is less than or equal to the current end time.

Hint 3

If you want to avoid explicit Python loops, consider using a cumulative maximum of the end times to identify where new intervals begin.

Follow-up questions

  • How would you modify your solution if intervals were considered overlapping only if they shared at least 5 minutes of time?
  • What is the time complexity of your approach, and can you optimize it if the DataFrame is already sorted by `start_time`?
  • How would you approach this problem if the data was too large to fit into memory, and you had to process it using Spark or SQL?