Watch the video solution for Find Overlapping Shifts, a medium level problem involving Database. This walkthrough by Everyday Data Science has 631 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 | 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.
| 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 |
