Watch the video solution for Find Overlapping Shifts II, a hard level problem involving Database. This walkthrough by Everyday Data Science has 914 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
Return the result table ordered by employee_id in ascending order.
The query result format is in the following example.
Example:
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:
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.
Problem Overview: You’re given shift records with start and end times and need to identify cases where two shifts overlap in time. The task is essentially interval overlap detection inside a relational dataset, which is common in scheduling systems and workforce analytics.
Approach 1: Direct Self Join (O(n²) time, O(1) extra space)
The most straightforward way is a self join on the shifts table. For two rows s1 and s2, an overlap exists if s1.start_time < s2.end_time and s2.start_time < s1.end_time. The query joins the table with itself and filters rows that satisfy this interval condition while avoiding duplicates using an ID comparison. This works because overlapping intervals always satisfy the cross-boundary condition above. However, the join compares many combinations, which leads to O(n²) comparisons on large datasets.
Approach 2: Merge + Join (O(n log n) time, O(n) space)
A more scalable approach merges continuous or adjacent shifts first, then performs the overlap check. Start by ordering shifts by employee and start time. Using window functions such as LAG or grouping techniques, merge contiguous intervals that belong to the same employee. This reduces redundant comparisons by collapsing fragmented schedules into normalized ranges.
After normalization, run a self join between the merged intervals to detect overlaps using the same interval condition (a.start < b.end AND b.start < a.end). Because the dataset is smaller and pre-ordered, the database optimizer performs significantly fewer comparisons. The sorting step dominates runtime, giving roughly O(n log n) complexity with O(n) intermediate storage.
This pattern mirrors the classic interval merge technique used in interval problems and combines it with relational joins from database queries. Window functions and ordering strategies are also common in advanced SQL query optimization tasks.
Recommended for interviews: Interviewers expect the interval-overlap logic to be correct first, typically shown with a simple self join. The stronger solution merges intervals before joining, which demonstrates understanding of query optimization and interval normalization. That version scales better and reflects real production query design.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Self Join | O(n²) | O(1) | Small datasets or when a quick SQL overlap check is sufficient |
| Merge + Join | O(n log n) | O(n) | Large scheduling tables where shifts may be fragmented and normalization reduces comparisons |
