Find overlapping shifts ii

# Table: EmployeeShifts
# 
# +------------------+----------+
# | Column Name      | Type     |
# +------------------+----------+
# | employee_id      | int      |
# | start_time       | datetime |
# | end_time         | datetime |
# +------------------+----------+
# (employee_id, start_time) is the unique key for this table.
# This table contains information about the shifts worked by employees, including the start time, and end time.
# 
# Write a solution to analyze overlapping shifts for each employee. Two shifts are considered overlapping if they occur on the same date and one shift's end_time is later than another shift's start_time.
# 
# For each employee, calculate the following:
# 
# The maximum number of shifts that overlap at any given time.
# 
# The total duration of all overlaps in minutes.
# 
# Return the result table ordered by employee_id in ascending order.
# 
# The query result format is in the following example.
#
# Example 1:
# Input:
# EmployeeShifts table:
# +-------------+---------------------+---------------------+
# | employee_id | start_time          | end_time            |
# +-------------+---------------------+---------------------+
# | 1           | 2023-10-01 09:00:00 | 2023-10-01 17:00:00 |
# | 1           | 2023-10-01 15:00:00 | 2023-10-01 23:00:00 |
# | 1           | 2023-10-01 16:00:00 | 2023-10-02 00:00:00 |
# | 2           | 2023-10-01 09:00:00 | 2023-10-01 17:00:00 |
# | 2           | 2023-10-01 11:00:00 | 2023-10-01 19:00:00 |
# | 3           | 2023-10-01 09:00:00 | 2023-10-01 17:00:00 |
# +-------------+---------------------+---------------------+
# Output:
# +-------------+---------------------------+------------------------+
# | employee_id | max_overlapping_shifts    | total_overlap_duration |
# +-------------+---------------------------+------------------------+
# | 1           | 3                         | 600                    |
# | 2           | 2                         | 360                    |
# | 3           | 1                         | 0                      |
# +-------------+---------------------------+------------------------+
# Explanation:
# Employee 1 has 3 shifts:
# 2023-10-01 09:00:00 to 2023-10-01 17:00:00
# 2023-10-01 15:00:00 to 2023-10-01 23:00:00
# 2023-10-01 16:00:00 to 2023-10-02 00:00:00
# The maximum number of overlapping shifts is 3 (from 16:00 to 17:00). The total overlap duration is: - 2 hours (15:00-17:00) between 1st and 2nd shifts - 1 hour (16:00-17:00) between 1st and 3rd shifts - 7 hours (16:00-23:00) between 2nd and 3rd shifts Total: 10 hours = 600 minutes
# Employee 2 has 2 shifts:
# 2023-10-01 09:00:00 to 2023-10-01 17:00:00
# 2023-10-01 11:00:00 to 2023-10-01 19:00:00
# The maximum number of overlapping shifts is 2. The total overlap duration is 6 hours (11:00-17:00) = 360 minutes.
# Employee 3 has only 1 shift, so there are no overlaps.
# The output table contains the employee_id, the maximum number of simultaneous overlaps, and the total overlap duration in minutes for each employee, ordered by employee_id in ascending order.

import pandas as pd

def calculate_shift_overlaps(employee_shifts: pd.DataFrame) -> pd.DataFrame:
  results = []
  for emp_id, group in employee_shifts.groupby('employee_id'):
    shifts = list(zip(group['start_time'], group['end_time']))
    # Max overlapping using sweep line
    events = []
    for s, e in shifts:
      events.append((s, 1))
      events.append((e, -1))
    events.sort()
    max_overlap = 0
    cur = 0
    for _, delta in events:
      cur += delta
      max_overlap = max(max_overlap, cur)

    # Total overlap duration: sum of pairwise overlaps
    total_minutes = 0
    for i in range(len(shifts)):
      for j in range(i + 1, len(shifts)):
        overlap_start = max(shifts[i][0], shifts[j][0])
        overlap_end = min(shifts[i][1], shifts[j][1])
        if overlap_start < overlap_end:
          total_minutes += int((overlap_end - overlap_start).total_seconds() / 60)

    results.append({
      'employee_id': emp_id,
      'max_overlapping_shifts': max_overlap,
      'total_overlap_duration': total_minutes
    })
  return pd.DataFrame(results).sort_values('employee_id')