LeetCode 3268 - Find Overlapping Shifts II

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

The problem asks us to analyze shift overlaps for employees. We are given a table EmployeeShifts with columns employee_id, start_time, and end_time. Each row represents one work shift for an employee. Two shifts are considered overlapping if they occur on the same date and the end_time of one shift is later than the start_time of another shift.

For each employee, we need to calculate two things: the maximum number of shifts overlapping at any single moment, and the total duration in minutes during which any overlaps occur. The result should be ordered by employee_id ascending.

The key constraints are:

Shifts can span multiple hours and potentially multiple days.
Each (employee_id, start_time) pair is unique.
Overlaps must be considered per date, so a shift that crosses midnight should be handled carefully.
The number of shifts per employee can vary, so the solution must scale efficiently.

Edge cases that can trip up a naive solution include:

Shifts that cross midnight into the next day.
Employees with only one shift (should return 0 overlaps).
Multiple shifts starting or ending at exactly the same time.

Approaches

Brute Force

A brute-force approach would compare every shift against every other shift for the same employee and the same date. For each pair of shifts, we could calculate overlap duration if any exists and keep track of the maximum number of overlaps at any moment using an interval counting method. While correct, this approach would involve O(n^2) comparisons per employee, which becomes inefficient if an employee has many shifts.

Optimal Approach

The optimal approach leverages the sweep line algorithm, commonly used in interval overlap problems. The main idea is to treat each shift start as +1 and each shift end as -1 in a timeline. Sorting these events allows us to efficiently compute the number of overlapping shifts at each point in time. Additionally, we can accumulate the total duration whenever overlaps are present. By separating shifts by employee and date, we ensure correctness across multiple days. This reduces the time complexity to O(n log n) for sorting events per employee per day.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2) per employee	O(1)	Compare every shift pair for overlaps
Optimal	O(n log n) per employee	O(n)	Sweep line with event sorting

Algorithm Walkthrough

For each employee, split shifts by the date of the shift (truncate start_time to get the date). If a shift crosses midnight, split it into multiple segments for each date it touches.
For each date, create a list of events: each start_time is a +1 event, each end_time is a -1 event.
Sort events by timestamp. For ties, process start_time before end_time.
Initialize counters: current_overlap = 0, max_overlap = 0, total_overlap_minutes = 0, prev_time = None.
Iterate through events. For each event:

If current_overlap >= 2 (more than 1 shift), add the duration since prev_time to total_overlap_minutes.
Update current_overlap based on whether the event is +1 or -1.
Update max_overlap if current_overlap exceeds it.
Update prev_time to current event time.

After processing all dates for an employee, record the employee's max_overlap and total_overlap_minutes.
Return all results ordered by employee_id.

Why it works: Sorting events ensures we process time in chronological order. Counting +1 and -1 updates the number of overlapping shifts accurately. By only counting durations when current_overlap >= 2, we correctly accumulate overlap times. This approach efficiently calculates both maximum simultaneous overlaps and total overlap duration.

Python Solution

from typing import List
from collections import defaultdict
from datetime import datetime, timedelta

class Solution:
    def findOverlappingShifts(self, shifts: List[dict]) -> List[dict]:
        result = []
        employees = defaultdict(list)

        # Split shifts per employee
        for s in shifts:
            employees[s['employee_id']].append((s['start_time'], s['end_time']))

        for emp_id in sorted(employees.keys()):
            events = []
            # Split shifts per day
            for start, end in employees[emp_id]:
                start_dt = datetime.fromisoformat(start)
                end_dt = datetime.fromisoformat(end)
                current = start_dt
                while current.date() < end_dt.date():
                    # Event until midnight
                    midnight = datetime.combine(current.date() + timedelta(days=1), datetime.min.time())
                    events.append((current, 1))
                    events.append((midnight, -1))
                    current = midnight
                # Last segment on the same day
                events.append((current, 1))
                events.append((end_dt, -1))

            # Sweep line
            events.sort()
            current_overlap = 0
            max_overlap = 0
            total_overlap = 0
            prev_time = None

            for time, delta in events:
                if prev_time and current_overlap >= 2:
                    total_overlap += int((time - prev_time).total_seconds() // 60)
                current_overlap += delta
                max_overlap = max(max_overlap, current_overlap)
                prev_time = time

            result.append({
                'employee_id': emp_id,
                'max_overlapping_shifts': max_overlap,
                'total_overlap_duration': total_overlap
            })

        return result

Explanation: We first group shifts by employee, then split any shift crossing midnight into multiple segments per date. We build events for the sweep line, sort them, and iterate to track overlapping shifts and total overlap duration. The maximum overlap is updated whenever a new maximum is encountered. Total overlap is accumulated only when current_overlap >= 2.

Go Solution

package main

import (
    "sort"
    "time"
)

type Shift struct {
    EmployeeID int
    StartTime  time.Time
    EndTime    time.Time
}

type Result struct {
    EmployeeID            int
    MaxOverlappingShifts  int
    TotalOverlapDuration  int
}

func FindOverlappingShifts(shifts []Shift) []Result {
    empMap := make(map[int][]Shift)
    for _, s := range shifts {
        empMap[s.EmployeeID] = append(empMap[s.EmployeeID], s)
    }

    var res []Result
    empIDs := make([]int, 0, len(empMap))
    for id := range empMap {
        empIDs = append(empIDs, id)
    }
    sort.Ints(empIDs)

    for _, emp := range empIDs {
        var events []struct {
            Time time.Time
            Delta int
        }

        for _, s := range empMap[emp] {
            start := s.StartTime
            end := s.EndTime
            current := start
            for current.Truncate(24 * time.Hour).Before(end.Truncate(24 * time.Hour)) {
                midnight := time.Date(current.Year(), current.Month(), current.Day()+1, 0, 0, 0, 0, current.Location())
                events = append(events, struct{Time time.Time; Delta int}{current, 1})
                events = append(events, struct{Time time.Time; Delta int}{midnight, -1})
                current = midnight
            }
            events = append(events, struct{Time time.Time; Delta int}{current, 1})
            events = append(events, struct{Time time.Time; Delta int}{end, -1})
        }

        sort.Slice(events, func(i, j int) bool {
            if events[i].Time.Equal(events[j].Time) {
                return events[i].Delta > events[j].Delta
            }
            return events[i].Time.Before(events[j].Time)
        })

        currentOverlap := 0
        maxOverlap := 0
        totalOverlap := 0
        var prevTime time.Time

        for i, e := range events {
            if i != 0 && currentOverlap >= 2 {
                totalOverlap += int(e.Time.Sub(prevTime).Minutes())
            }
            currentOverlap += e.Delta
            if currentOverlap > maxOverlap {
                maxOverlap = currentOverlap
            }
            prevTime = e.Time
        }

        res = append(res, Result{emp, maxOverlap, totalOverlap})
    }

    return res
}

Explanation: The Go implementation mirrors the Python logic but uses slices and structs. The main difference is explicit type definitions and careful handling of time.Time operations. The sorting logic ensures start events come before end events for equal timestamps.

Worked Examples

Employee 1 Example:

Shifts: 09:00-17:00, 15:00-23:00, 16:00-00:00

Time	Overlap Count	Total Overlap Accumulated
09:00	1	0
15:00	2	0
16:00	3	60
17:00	2	120
23:00	1	480
00:00	0	600