Merge Intervals: Introduction

Let’s go over the Merge Intervals pattern, its real-world applications and some problems we can solve with it.

We'll cover the following

Overview#

The merge intervals pattern deals with problems involving overlapping intervals. Each interval is represented by a start and an end time. For example, an interval of [10,20][10, 20] seconds means that the interval starts at 1010 seconds and ends at 2020 seconds, such that both 1010 and time 2020 are included in the interval.

The most common problems solved using this pattern are scheduling problems.

The key to understanding this pattern and exploiting its power lies in understanding how any two intervals may overlap. The illustration below shows the six different ways in which two intervals can relate to each other:

Created with Fabric.js 3.6.6 Interval 1 Interval 2 1. Intervals 1 and 2 don't overlap. Interval 1 ends before the start of Interval 2:

1 of 6

Created with Fabric.js 3.6.6 Interval 1 Interval 2 2. Interval 1 and Interval 2 overlap. Interval 2 ends after Interval 1:

2 of 6

Created with Fabric.js 3.6.6 Interval 1 Interval 2 3. Interval 2 completely overlaps Interval 1:

3 of 6

Created with Fabric.js 3.6.6 Interval 1 Interval 2 4. Interval 1 and Interval 2 overlap. Interval 1 ends after Interval 2:

4 of 6

Created with Fabric.js 3.6.6 Interval 1 Interval 2 5. Interval 1 completely overlaps Interval 2:

5 of 6

Created with Fabric.js 3.6.6 Interval 1 Interval 2 6. Interval 1 and 2 don't overlap. Interval 1 starts after the end of Interval 2:

6 of 6

Examples#

The following examples illustrate some problems that can be solved with this approach:

Created with Fabric.js 3.6.6 Intervals [1, 5] [4, 6] [7, 9] [8, 9] [9, 10] Merge overlapping intervals

1 of 2

Created with Fabric.js 3.6.6 5 15 20 25 30 10 Result = False 0 5 10 15 20 Result = True 0 Overlapping Intervals Given an array of meeting time intervals, determine if a personcould attend all meetings. Intervals [0, 30] [5, 10] [15, 20] Intervals [1, 3] [10, 15] [15,20] Two intervals overlap with the first interval, hence the person cannot attend all the meetings. [1, 3] The two intervals don't overlap, hence the personcan attend both meetings. [5, 10] [0, 30] Meeting rooms Example 1 Example 2 [10, 15]

2 of 2

Does my problem match this pattern?#

  • Yes, if both of these conditions are fulfilled:
    • The input data is an array of intervals.
    • The problem requires dealing with overlapping intervals, either to find their intersection, their union, or the gaps between them. This may be required as the final goal, or as an intermediate step in the computation of intervals.
  • No, if either of these conditions is fulfilled:
    • The order of the intervals in the result is not significant.
    • The input list of intervals is not sorted. In such a situation, we would prefer to use some other technique to efficiently solve the problem.

Real-world problems#

Many problems in the real world use the merge intervals pattern. Let’s look at some examples.

  • Display busy schedule: Display the busy hours of a user to other users without revealing the individual meeting slots in a calendar.

  • Schedule a new meeting: Add a new meeting to the tentative meeting schedule of a user in such a way that no two meetings overlap each other.

  • Task scheduling in operating systems (OS): Schedule tasks for the OS based on task priority and the free slots in the machine’s processing schedule.

Strategy time!#

Match the problems that can be solved using the merge intervals pattern.

Note: Select a problem in the left-hand column by clicking it, and then click one of the two options in the right-hand column.

Match The Answer
Select an option from the left-hand side

Find the 4th4^{th} largest element in an array

Explanation

Merge Intervals

Schedule 3 interviews for an interviewer in one day

Explanation

Some other pattern

Find the intersection of two intervals

Explanation

Find the 3rd3^{rd} closest point to the origin

Explanation

Task Scheduler