Merge Overlapping Intervals

The 'Meeting Room Merger' problem asks you to consolidate overlapping time intervals, which is a common scenario in scheduling applications. Mastering this problem demonstrates your ability to work with interval data and optimize algorithms for efficiency, crucial for software engineering roles.

arrayintervalssortinggreedy algorithmmerging

Problem Statement

You are given a list of meeting room bookings, where each booking is represented as a pair of integers: [start_time, end_time]. Your task is to merge all overlapping meeting room bookings into a set of non-overlapping intervals, representing the consolidated schedule. Return the new list of merged intervals.

Example 1

Input: [[1, 3], [2, 6], [8, 10], [15, 18]]

Output: [[1, 6], [8, 10], [15, 18]]

The intervals [1, 3] and [2, 6] overlap, so they are merged into [1, 6]. The other intervals do not overlap with this or each other, so they remain separate.

Example 2

Input: [[1, 4], [4, 5]]

Output: [[1, 5]]

The intervals [1, 4] and [4, 5] overlap at the boundary (4), so they are merged into [1, 5].

Constraints

-The input list will contain at least one meeting room booking.
-All start and end times are non-negative integers.
-For each meeting room booking, the start time will be less than or equal to the end time.
-The input list may not be sorted.

Brute Force Approach

Imagine you're a receptionist manually checking each meeting room booking against all the others. For every pair of meetings, you'd check if they overlap. If they do, you'd merge them and repeat the process. This approach has to re-check merged intervals, making it inefficient. This involves nested loops comparing each interval to every other interval.

TimeO(n^2)

SpaceO(1)

Ready to practice?

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

Practice This Problem