Merge Intervals (Medium)

Good evening! Here's our prompt for today.

You may see this problem at Doordash, Tableau Software, Yelp, Workday, Spotify, Netskope, Appian, Akamai, Docusign, Proofpoint, At T, Mcafee, Electronic Arts, and Zuora.

This is a classic interview question that is used in a lot in technical interviews, frequently in the form of a calendar or meeting management application. As such, we'll also assume the same use case, as it's easier to visualize.

Suppose we're given a few arrays, like [1, 4], [2, 5], [7, 10], [12, 16], representing time intervals. The elements within the arrays represent a start time and end time of a meeting. So an array "time range" of [1, 4] would mean that the event starts at 1-o'clock and ends at 4-o'clock.

Now, what if we wanted to merge any overlapping meetings? If one meeting runs into the time of another, we'll want to combine them into one. As such, [1, 4] and [2, 5], who overlap between 4 o'clock and 5 o'clock, would be combined into [1, 5].

For the above example of [1, 4], [2, 5], [7, 10], [12, 16], we would want to return [1, 5], [7, 10], [12, 16]. Can you write a method that will do this?

Constraints

• Size of array ranges <= 100000
• The array will always contain integer values between -1000000000 and 1000000000
• Expected time complexity : O(n)
• Expected space complexity : O(n)