Skip to main content
Talentd

Find Overlapping Shifts - Solution & Explanation

MediumPremiumFree on FleetCodeDatabase5 min read
Practice this problem

Problem Statement

Table: EmployeeShifts

+------------------+---------+
| Column Name      | Type    |
+------------------+---------+
| employee_id      | int     |
| start_time       | time    |
| end_time         | time    |
+------------------+---------+
(employee_id, start_time) is the unique key for this table.
This table contains information about the shifts worked by employees, including the start and end times on a specific date.

Write a solution to count the number of overlapping shifts for each employee. Two shifts are considered overlapping if one shift’s end_time is later than another shift’s start_time.

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           | 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 |
+-------------+------------+----------+

Output:

+-------------+--------------------+
| employee_id | overlapping_shifts |
+-------------+--------------------+
| 1           | 2                  |
| 2           | 1                  |
| 4           | 1                  |
+-------------+--------------------+

Explanation:

  • Employee 1 has 3 shifts:
    • 08:00:00 to 12:00:00
    • 11:00:00 to 15:00:00
    • 14:00:00 to 18:00:00
    The first shift overlaps with the second, and the second overlaps with the third, resulting in 2 overlapping shifts.
  • Employee 2 has 2 shifts:
    • 09:00:00 to 17:00:00
    • 16:00:00 to 20:00:00
    These shifts overlap with each other, resulting in 1 overlapping shift.
  • Employee 3 has 3 shifts:
    • 10:00:00 to 12:00:00
    • 13:00:00 to 15:00:00
    • 16:00:00 to 18:00:00
    None of these shifts overlap, so Employee 3 is not included in the output.
  • Employee 4 has 2 shifts:
    • 08:00:00 to 10:00:00
    • 09:00:00 to 11:00:00
    These shifts overlap with each other, resulting in 1 overlapping shift.

The output shows the employee_id and the count of overlapping shifts for each employee who has at least one overlapping shift, ordered by employee_id in ascending order.

Approach Overview

Problem Overview: The task is to detect employees who have work shifts that overlap in time. Each shift has a start and end timestamp. Two shifts overlap if one shift starts before the other ends and ends after the other starts.

Approach 1: Self-Join + Group Counting (O(n^2) time, O(1) extra space)

The core idea is to compare every shift with other shifts belonging to the same employee. A self join on the shifts table pairs each shift with another shift from the same employee. An overlap exists when s1.start_time < s2.end_time and s2.start_time < s1.end_time. To avoid matching the same row with itself, include a condition like s1.shift_id < s2.shift_id. After generating overlapping pairs, use GROUP BY on the employee or shift identifier and count the matches.

This pattern is common in SQL interview questions involving interval comparisons. The self-join exposes all potential overlaps, while grouping helps aggregate the results into the final output format required by the problem.

Approach 2: Pandas Self Merge + Boolean Filtering (O(n^2) time, O(n^2) space)

In Pandas, the equivalent technique uses DataFrame.merge() to join the dataset with itself on the employee identifier. This creates candidate pairs of shifts. Apply boolean filters to keep only rows where the overlap condition holds: (start_x < end_y) & (start_y < end_x). Exclude identical rows by ensuring the shift identifiers differ.

Once overlapping pairs are identified, use groupby() and aggregation to compute counts or produce the final output structure. This mirrors the SQL strategy but relies on vectorized operations from Pandas and common database join patterns.

Recommended for interviews: The self-join approach is the expected solution. Interviewers want to see that you recognize the classic interval-overlap condition and know how to implement it using joins and filtering. Brute-force comparisons demonstrate understanding, but structuring the logic with a proper self-join and grouping shows stronger SQL fluency.

Solution

We first use a self-join to connect the EmployeeShifts table to itself. The join condition ensures that we only compare shifts belonging to the same employee and check if there is any overlap between shifts.

  1. t1.start_time < t2.start_time: Ensures that the start time of the first shift is earlier than the start time of the second shift.
  2. t1.end_time > t2.start_time: Ensures that the end time of the first shift is later than the start time of the second shift.

Next, we group the data by employee_id and count the number of overlapping shifts for each employee.

Finally, we filter out employees with overlapping shift counts greater than 0 and sort the results in ascending order by employee_id.

Code

MySQLPandas

MySQL

Pandas

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Self-Join + Overlap Condition (SQL)O(n^2)O(1)Standard SQL solution for detecting overlapping time intervals in relational tables
Self Merge + Boolean Filtering (Pandas)O(n^2)O(n^2)When solving database-style problems in Python using Pandas

Video Solution

Leetcode MEDIUM 3262 - SELF JOINs in SQL - Find Overlapping Shifts | Everyday Data Science • Everyday Data Science • 666 views views

Frequently Asked Questions

Is Find Overlapping Shifts easy or hard?
Find Overlapping Shifts is considered a medium difficulty database problem. The challenge comes from recognizing the correct interval overlap condition and applying a self-join without accidentally matching rows with themselves.
Find Overlapping Shifts Python/Java solution
SQL is the primary solution format for this problem, but Python solutions use Pandas with DataFrame.merge() and boolean filtering to replicate the same overlap logic. Java implementations typically rely on database queries rather than in-memory algorithms.
How to solve Find Overlapping Shifts in O(n)?
Pure O(n) solutions are uncommon in SQL because overlap detection requires comparing intervals. Database engines optimize joins using indexes on employee_id and timestamps, which reduces practical runtime, but the logical comparison complexity remains O(n^2).
What is the best approach for Find Overlapping Shifts?
The standard solution uses a self-join on the shifts table combined with an interval overlap condition. Two shifts overlap if start1 < end2 and start2 < end1. After joining rows from the same employee, filtering and grouping identify the overlapping shifts efficiently.
Is Find Overlapping Shifts asked at Google/Amazon/Meta?
Interval overlap detection is a common database and analytics interview pattern used by companies like Amazon and Google. Variations appear in scheduling systems, booking conflicts, and employee shift management problems.
What data structure is used in Find Overlapping Shifts?
The problem primarily uses relational database tables and join operations. Conceptually it relies on interval comparison logic, implemented through SQL self-joins or DataFrame merges in Pandas.
What is the time complexity of Find Overlapping Shifts?
The typical self-join solution runs in O(n^2) time because each shift may be compared with many other shifts. Space complexity is O(1) in SQL aside from query execution overhead, though Pandas implementations may use O(n^2) memory for the merged dataframe.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary