Merge overlapping time intervals

Q: Merge overlapping time intervals

This question evaluates a candidate's understanding of interval arithmetic, sorting and array manipulation, specifically the ability to merge overlapping ranges efficiently.

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

Problem

You are given a list of closed intervals intervals, where each interval is [start, end] and start <= end.

Merge all intervals that overlap and return the resulting list of merged intervals.

Two intervals [a, b] and [c, d] are considered overlapping if c <= b (i.e., touching at an endpoint also counts as overlapping).

Input

intervals : a list of n intervals, each represented as two integers [start, end] .

Output

A list of merged, non-overlapping intervals, sorted by increasing start .

Constraints

0 <= n <= 1e5
-1e9 <= start <= end <= 1e9

Example

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

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