Find Overlapping Shifts II

Problem

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 inascending order.

The query result format is in the following example.

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


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.

Solution

Method 1 – Sweep Line Algorithm with Event Processing

Intuition

To find the maximum number of overlapping shifts and the total overlap duration for each employee, we can treat each shift’s start and end as events. By processing these events in order, we can track how many shifts are active at any time and sum up the durations where more than one shift overlaps.

Approach

For each employee, group their shifts by date (since overlaps are only counted on the same date).
For each date:
- Create a list of events: each shift’s start (+1) and end (-1).
- Sort all events by time.
- Sweep through the events, maintaining a counter of active shifts.
- Track the maximum number of active shifts.
- For total overlap duration, whenever the active count is 2 or more, add the time difference to the total.
Sum the total overlap duration and maximum overlap for all dates for each employee.
Return the results ordered by employee_id.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50


WITH events AS (
  SELECT
    employee_id,
    DATE(start_time) AS day,
    start_time AS time,
    1 AS delta
  FROM EmployeeShifts
  UNION ALL
  SELECT
    employee_id,
    DATE(start_time) AS day,
    end_time AS time,
    -1 AS delta
  FROM EmployeeShifts
),
ordered_events AS (
  SELECT
    employee_id,
    day,
    time,
    delta
  FROM events
  ORDER BY employee_id, day, time
),
sweep AS (
  SELECT
    employee_id,
    day,
    time,
    delta,
    SUM(delta) OVER (PARTITION BY employee_id, day ORDER BY time, delta DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS active
  FROM ordered_events
),
intervals AS (
  SELECT
    employee_id,
    day,
    time AS start_time,
    LEAD(time) OVER (PARTITION BY employee_id, day ORDER BY time) AS end_time,
    active
  FROM sweep
)
SELECT
  employee_id,
  MAX(active) AS max_overlapping_shifts,
  COALESCE(SUM(TIMESTAMPDIFF(MINUTE, start_time, end_time) * (active > 1)), 0) AS total_overlap_duration
FROM intervals
WHERE end_time IS NOT NULL
GROUP BY employee_id
ORDER BY employee_id;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50


WITH events AS (
  SELECT
    employee_id,
    DATE(start_time) AS day,
    start_time AS time,
    1 AS delta
  FROM EmployeeShifts
  UNION ALL
  SELECT
    employee_id,
    DATE(start_time) AS day,
    end_time AS time,
    -1 AS delta
  FROM EmployeeShifts
),
ordered_events AS (
  SELECT
    employee_id,
    day,
    time,
    delta
  FROM events
  ORDER BY employee_id, day, time
),
sweep AS (
  SELECT
    employee_id,
    day,
    time,
    delta,
    SUM(delta) OVER (PARTITION BY employee_id, day ORDER BY time, delta DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS active
  FROM ordered_events
),
intervals AS (
  SELECT
    employee_id,
    day,
    time AS start_time,
    LEAD(time) OVER (PARTITION BY employee_id, day ORDER BY time) AS end_time,
    active
  FROM sweep
)
SELECT
  employee_id,
  MAX(active) AS max_overlapping_shifts,
  COALESCE(SUM(EXTRACT(EPOCH FROM (end_time - start_time))/60 * (active > 1)::int), 0) AS total_overlap_duration
FROM intervals
WHERE end_time IS NOT NULL
GROUP BY employee_id
ORDER BY employee_id;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution:
    def find_overlapping_shifts(self, df):
        # df has columns: employee_id, start_time, end_time (as pd.Timestamp)
        import pandas as pd
        ans = []
        for eid, group in df.groupby('employee_id'):
            max_overlap = 0
            total_overlap = 0
            # Group by date
            group = group.copy()
            group['date'] = group['start_time'].dt.date
            for day, shifts in group.groupby('date'):
                events = []
                for _, row in shifts.iterrows():
                    events.append((row['start_time'], 1))
                    events.append((row['end_time'], -1))
                events.sort()
                active = 0
                prev_time = None
                for time, delta in events:
                    if prev_time is not None and active > 1:
                        total_overlap += int((time - prev_time).total_seconds() // 60)
                    active += delta
                    max_overlap = max(max_overlap, active)
                    prev_time = time
            ans.append({'employee_id': eid, 'max_overlapping_shifts': max_overlap, 'total_overlap_duration': total_overlap})
        return pd.DataFrame(ans).sort_values('employee_id')

Complexity

⏰ Time complexity: O(n log n) per employee, where n is the number of shifts, due to sorting events for each employee and date.
🧺 Space complexity: O(n) for storing events and intermediate results per employee.

Problem#

Example 1:#

Solution#

Method 1 – Sweep Line Algorithm with Event Processing#

Intuition#

Approach#

Code#

Complexity#