Merge overlapping intervals

Q: Merge overlapping intervals

This question evaluates proficiency in interval manipulation, array-based data structures, algorithm design, and time/space complexity analysis, focusing on merging overlapping numeric ranges into non-overlapping sorted intervals.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given an array of intervals, where each interval is represented as a pair of integers [start, end] with start <= end. The intervals may be unsorted and may overlap.

Task:

Merge all overlapping intervals.
Return a new array of non-overlapping intervals that cover exactly the same ranges as the input.
The result should be sorted in ascending order by interval start.

Example:

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

Constraints (you may assume reasonable values if not specified by the interviewer):

1 <= number of intervals <= 10^4
Interval endpoints are integers in a range such as [-10^9, 10^9].

Design an algorithm to perform this merge efficiently and discuss its time and space complexity.

Merge overlapping intervals

Overview

Comments (0)