LeetCode 3262 - Find Overlapping Shifts

The problem requires counting overlapping shifts for each employee from a database table called EmployeeShifts. Each row in this table represents a single shift worked by an employee, with a starttime and an endtime.

leetcodemediumdatabase

LeetCode Problem 3262

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem requires counting overlapping shifts for each employee from a database table called EmployeeShifts. Each row in this table represents a single shift worked by an employee, with a start_time and an end_time. Two shifts are considered overlapping if one shift ends after another shift starts, meaning that their time intervals intersect.

The goal is to return a result table that shows each employee_id who has at least one overlapping shift, along with the count of overlapping shifts. The result should be ordered by employee_id in ascending order.

The input guarantees that (employee_id, start_time) is unique, which means there are no duplicate shifts for an employee starting at the same time. Edge cases include employees with only one shift (no possible overlap), shifts that exactly touch but do not overlap (end time equals start time), and employees with multiple shifts fully overlapping each other. The time values are in HH:MM:SS format and can be compared directly.

Approaches

A brute-force approach would compare every shift of an employee with every other shift of the same employee. For each pair of shifts, if the end_time of one shift is later than the start_time of another shift, we would count it as an overlap. While correct, this approach is inefficient, as it requires examining all pairs, which leads to a quadratic time complexity relative to the number of shifts per employee.

A more optimal approach leverages sorting. By sorting each employee’s shifts by start_time, we can iterate over the shifts and maintain the end_time of the previous shift. If the start_time of the current shift is earlier than the previous end_time, an overlap is detected. This reduces redundant comparisons and efficiently counts overlaps for each employee in linear time relative to the number of shifts after sorting.

Approach Time Complexity Space Complexity Notes
Brute Force O(N^2) O(1) Compare every pair of shifts per employee
Optimal O(N log N) O(1) Sort shifts by start_time per employee, then scan linearly

Algorithm Walkthrough

  1. Group all shifts by employee_id so that we can process each employee independently.

  2. For each employee, sort their shifts by start_time in ascending order.

  3. Initialize a counter for overlapping shifts to zero and a variable prev_end to track the end time of the previous shift.

  4. Iterate over the sorted shifts:

  5. If the current shift's start_time is earlier than prev_end, increment the overlapping shifts counter.

  6. Update prev_end to be the maximum of the current shift's end_time and prev_end to account for fully overlapping shifts.

  7. Only include employees with at least one overlap in the final result.

  8. Return the result sorted by employee_id.

Why it works: Sorting ensures that we only need to compare the current shift with the most recent previous shift. By keeping track of the maximum end_time, we correctly handle chains of overlapping shifts without redundant comparisons.

Python Solution

import pandas as pd

def find_overlapping_shifts(employee_shifts: pd.DataFrame) -> pd.DataFrame:
    result = []
    for employee_id, group in employee_shifts.groupby('employee_id'):
        shifts = group.sort_values('start_time')
        prev_end = None
        overlap_count = 0
        for _, row in shifts.iterrows():
            if prev_end and row['start_time'] < prev_end:
                overlap_count += 1
            prev_end = max(prev_end, row['end_time']) if prev_end else row['end_time']
        if overlap_count > 0:
            result.append({'employee_id': employee_id, 'overlapping_shifts': overlap_count})
    return pd.DataFrame(result).sort_values('employee_id')

This Python solution groups the data by employee_id and sorts each employee’s shifts by start_time. The iteration keeps track of the prev_end time, incrementing the overlap counter when a shift overlaps with the previous one. Only employees with at least one overlap are added to the result.

Go Solution

package main

import (
    "sort"
)

type Shift struct {
    EmployeeID int
    StartTime  string
    EndTime    string
}

type Result struct {
    EmployeeID        int
    OverlappingShifts int
}

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

    var results []Result
    for employeeID, sList := range employeeShifts {
        sort.Slice(sList, func(i, j int) bool {
            return sList[i].StartTime < sList[j].StartTime
        })
        overlapCount := 0
        prevEnd := ""
        for _, s := range sList {
            if prevEnd != "" && s.StartTime < prevEnd {
                overlapCount++
            }
            if prevEnd == "" || s.EndTime > prevEnd {
                prevEnd = s.EndTime
            }
        }
        if overlapCount > 0 {
            results = append(results, Result{EmployeeID: employeeID, OverlappingShifts: overlapCount})
        }
    }

    sort.Slice(results, func(i, j int) bool {
        return results[i].EmployeeID < results[j].EmployeeID
    })

    return results
}

In Go, the solution follows the same logic as Python. We group shifts by employee, sort them by StartTime, and track prevEnd. Go requires explicit map initialization and sorting functions, which is slightly more verbose but logically identical.

Worked Examples

Employee 1 Shifts

start_time end_time
08:00:00 12:00:00
11:00:00 15:00:00
14:00:00 18:00:00
  • Sorted shifts: same as above.
  • Compare 08:00-12:00 with 11:00-15:00 → overlap (prev_end 12:00 > start 11:00), count = 1
  • Compare 11:00-15:00 with 14:00-18:00 → overlap (prev_end 15:00 > start 14:00), count = 2

Employee 2 Shifts

start_time end_time
09:00:00 17:00:00
16:00:00 20:00:00
  • Sorted shifts: same as above.
  • Compare 09:00-17:00 with 16:00-20:00 → overlap (prev_end 17:00 > start 16:00), count = 1

Employee 3 Shifts

  • No overlaps detected; excluded from results.

Employee 4 Shifts

  • 08:00-10:00 overlaps with 09:00-11:00 → count = 1

Complexity Analysis

Measure Complexity Explanation
Time O(N log N) Sorting the shifts per employee dominates; iterating is linear
Space O(N) For grouping shifts per employee and storing results

The algorithm scales efficiently with the number of shifts due to sorting, and it avoids quadratic pairwise comparisons.

Test Cases

# test cases
import pandas as pd

shifts = pd.DataFrame([
    (1, "08:00:00", "12:00:00"),
    (1, "11:00:00", "15:00:00"),
    (1, "14:00:00", "18:00:00"),
    (2, "09:00:00", "17:00:00"),
    (2, "16:00:00", "20:00:00"),
    (3, "10:00:00", "12:00:00"),
    (3, "13:00:00", "15:00:00"),
    (3, "16:00:00", "18:00:00"),
    (4, "08:00:00", "10:00:00"),
    (4, "09:00:00", "11:00:00"),
], columns=["employee_id", "start_time", "end_time"])

res = find_overlapping_shifts(shifts)
assert res.loc[res['employee_id']==1, 'overlapping_shifts'].iloc[0] == 2  # Employee 1
assert res.loc[res['employee_id']==2, 'overlapping_shifts'].iloc[0] == 1  # Employee 2
assert 3 not in res['employee_id'].values  # Employee 3
assert res.loc[res['employee_id']==4, 'overlapping_shifts'].iloc[0] == 1  # Employee 4
Test Why
Employee 1 Chain of overlapping shifts
Employee 2 Single overlap between two shifts
Employee 3 No overlaps; ensures correct exclusion
Employee 4 Partial overlap with two shifts

Edge Cases

Single Shift Employee: An employee with only one shift cannot have overlaps. Our grouping logic naturally excludes them because the overlap counter remains zero.

**Shifts Touching but Not