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:
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.
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.
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.
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.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.
| Approach | Time | Space | When 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 |
Leetcode MEDIUM 3262 - SELF JOINs in SQL - Find Overlapping Shifts | Everyday Data Science • Everyday Data Science • 631 views views
Practice Find Overlapping Shifts with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor