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.
We can merge all the start_time and end_time for each employee_id and store them in table T. Then, by using the LEAD function, we calculate the next time period for each employee_id and store it in table P.
Next, we can join table P with the EmployeeShifts table to calculate the concurrent_count for each employee_id, which represents the number of overlapping time periods. This is stored in table S.
Finally, we can perform a self-join on the EmployeeShifts table to calculate the total_overlap_duration for each employee_id, representing the total overlapping time, and store it in table U.
Ultimately, we can join tables S and U to calculate the max_overlapping_shifts and total_overlap_duration for each employee_id.
Similar Problems:
MySQL
| 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 |
Leetcode HARD 3268 - SELF JOINs in SQL Explained - Find Overlapping Shifts 2 | Everyday Data Science • Everyday Data Science • 914 views views
Practice Find Overlapping Shifts II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor