Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

merge
overlapping
intervals problems

What is the merge overlapping intervals problem?

Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

In the merge overlapping intervals problem, we are given a group of time intervals and tasked with outputting mutually exclusive intervals. ​

svg viewer

Algorithm

The most efficient way to solve this problem is to use the stack structure:

  1. Sort the given list of time intervals in ascending order of starting time.
  2. Then, push the first time interval in the stack and compare the next interval with the one in the stack.
  3. If it’s overlapping, then merge them into one interval; otherwise, push it in the stack.
  4. In the end, the intervals left in the stack will be mutually exclusive.
1 of 7

Time Complexity

The naive approach would be to compare each interval with all the other intervals in the list; this approach would take O(n2)O(n^2) time. However, as mentioned above, the efficient approach ​would take O(nLogn)O(nLog n) time because we have to sort n intervals making it nlognnlogn time complexity.

RELATED TAGS

merge
overlapping
intervals problems
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring