Practice/Google/Leetcode 3262. Find Overlapping Shifts

Leetcode 3262. Find Overlapping Shifts

CodingMust

Problem

You are developing a scheduling system for a company that needs to detect conflicts in employee work schedules. Given a list of work shifts where each shift is represented as an interval [start, end] indicating the start and end times, return all pairs of shift indices that have overlapping time periods.

Two shifts overlap if they share any common time. Note that if one shift ends exactly when another begins (e.g., [1, 5] and [5, 10]), they are considered adjacent but not overlapping.

Return the result as a list of pairs [i, j] where i < j and shifts i and j overlap. The pairs should be sorted in ascending order.

Requirements

1. Return all pairs of shift indices that have time conflicts
2. Each pair should be represented as [i, j] where i < j
3. Shifts that touch at endpoints but don't overlap should not be included
4. The result should be sorted by the first index, then by the second index
5. Handle edge cases such as empty lists, single shifts, and identical time ranges

Constraints

• 0 <= shifts.length <= 1000
• shifts[i].length == 2
• 0 <= start_i < end_i <= 10^6
• Optimize for better than O(n²) time complexity when possible
• Space complexity should be reasonable for the output size

Examples

Example 1:

Input: shifts = [[1, 4], [2, 6], [8, 10]] Output: [[0, 1]] Explanation: Shift 0 (1-4) and Shift 1 (2-6) overlap during the time period [2, 4). Shift 2 (8-10) doesn't overlap with any other shift.

Example 2:

` Input: shifts = [[1, 3], [2, 5], [4, 7], [6, 8]] Output: [[0, 1], [1, 2], [2, 3]] Explanation:

• Shifts 0 and 1 overlap during [2, 3)
• Shifts 1 and 2 overlap during [4, 5)
• Shifts 2 and 3 overlap during [6, 7) `

Example 3:

Input: shifts = [[1, 5], [5, 10]] Output: [] Explanation: These shifts are adjacent but not overlapping since one ends exactly when the other begins.