Identify All Interval Overlaps

Given two lists of time intervals, find all the overlapping time periods between them. This problem tests your ability to work with interval data structures and algorithmic thinking.

arrayintervalstwo-pointerssorted-listtime-management

Problem Statement

You are given two lists of closed time intervals, schedule1 and schedule2. Each list is sorted in ascending order by the start time of the intervals, and within each list, no intervals overlap. Your task is to find all intervals where the time ranges in schedule1 and schedule2 overlap. Return a list of these overlapping intervals.

Example 1

Input: schedule1 = [[0, 5], [10, 15]], schedule2 = [[2, 6], [12, 18]]

Output: [[2, 5], [12, 15]]

The interval [0, 5] in schedule1 overlaps with [2, 6] in schedule2, resulting in the overlapping interval [2, 5]. The interval [10, 15] in schedule1 overlaps with [12, 18] in schedule2, resulting in the overlapping interval [12, 15].

Example 2

Input: schedule1 = [[1, 3], [5, 9]], schedule2 = [[2, 4], [6, 8]]

Output: [[2, 3], [6, 8]]

The interval [1, 3] in schedule1 overlaps with [2, 4] in schedule2, resulting in the overlapping interval [2, 3]. The interval [5, 9] in schedule1 overlaps with [6, 8] in schedule2, resulting in the overlapping interval [6, 8].

Constraints

-Each interval is represented as a list of two integers: [start, end].
-The start time of each interval is less than its end time (start < end).
-Both input lists are sorted in ascending order by the start time of the intervals.
-Within each input list, no two intervals overlap.
-The intervals contain non-negative integer values.

Brute Force Approach

The brute-force approach would be like checking every meeting in one schedule against every meeting in the other schedule to see if they collide. For each pair of intervals across the two schedules, you'd compare their start and end times to see if they overlap, and if so, record the overlapping segment. This involves comparing each interval in the first list with every interval in the second list.

TimeO(m*n)

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem