Merging Meeting Times

This is a popular algorithm problem that involves a list of integers which indicate meeting time slots in a calendar. The target is to return a merged list by merging the overlapping time slots.

Found it on InterviewCake. Although their descriptive solution was super helpful, the lack of visuals is what prompted me to write up this post. Since I Love Python, I am sticking to jargon specific to it. All of it should be pretty transferable to any other programming language!

Considering the time slots start from 9:00am, let’s imagine the input contains integers which are 30-minute blocks past 9.

For example:

(2, 3)  # Meeting from 10:00 – 10:30 am

Sample I/O:

Input:

[(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)]

Output

[(0, 1), (3, 8), (9, 12)]

Let’s analyze the I/O a bit more:

• Each tuple in the input list can be considered as specific time slots, for example — (3,5) indicates a meeting taking place from 10:30 to 11:30 (30 min blocks from 9:00)
• The input list might not be sorted. Sorting it seems to make life easier to solve this problem! So we already know we doing O(n logn)
• The output list contains the meeting slots merged and thus the list is more compact

The Pattern