Skip to main content
Talentd

Find Overlapping Shifts II - Solution & Explanation

HardPremiumFree on FleetCodeDatabase5 min read
Practice this problem

Problem Statement

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:

  1. The maximum number of shifts that overlap at any given time.
  2. The total duration of all overlaps in minutes.

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:

  • 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.

Approach Overview

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.

Solution

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:

Code

MySQL

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Self JoinO(n²)O(1)Small datasets or when a quick SQL overlap check is sufficient
Merge + JoinO(n log n)O(n)Large scheduling tables where shifts may be fragmented and normalization reduces comparisons

Video Solution

Leetcode HARD 3268 - SELF JOINs in SQL Explained - Find Overlapping Shifts 2 | Everyday Data Science • Everyday Data Science • 1,007 views views

Frequently Asked Questions

Is Find Overlapping Shifts II easy or hard?
Find Overlapping Shifts II is rated Hard because it combines interval reasoning with advanced SQL operations such as self joins, ordering, and window-based merging. Correct overlap conditions and query optimization are the main challenges.
Find Overlapping Shifts II Python/Java solution
This problem is categorized under database queries, so the standard solution uses SQL (MySQL). In application code like Python or Java, the same logic would involve sorting intervals and checking overlaps using interval comparison conditions.
How to solve Find Overlapping Shifts II in O(n log n)?
Sort shifts by employee and start time, then merge contiguous or overlapping intervals using window functions like LAG or grouping logic. After normalization, perform a self join on the merged intervals with the overlap condition start1 < end2 AND start2 < end1.
What is the best approach for Find Overlapping Shifts II?
The merge + join strategy is the most efficient. First normalize or merge adjacent shifts using ordering and window functions, then run a self join to detect interval overlaps using the condition start1 < end2 AND start2 < end1. This reduces redundant comparisons and scales better than a raw self join.
Is Find Overlapping Shifts II asked at Google/Amazon/Meta?
Interval overlap and scheduling queries are common interview themes at companies like Amazon, Google, and Meta. Variants appear in both SQL interviews and algorithm rounds where candidates detect overlapping time ranges efficiently.
What data structure is used in Find Overlapping Shifts II?
The core concept is interval processing. In SQL, this is implemented using relational tables, ordering, and window functions rather than traditional in-memory data structures. The overlap logic mirrors interval comparison used in algorithm problems.
What is the time complexity of Find Overlapping Shifts II?
The optimized SQL approach runs in roughly O(n log n) time due to sorting or window function ordering. A naive self join checks every pair of rows and can reach O(n²) comparisons on large tables.

Ready to solve this problem?

Practice Find Overlapping Shifts II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary