Merge Intervals for Multiple Streams | Dataford Interview Questions

Crusoe infrastructure telemetry can arrive as multiple independently ordered streams of active time ranges. Given several streams of intervals, return one consolidated list containing all overlapping intervals across every stream.

Each interval is represented as [start, end], where start <= end. Every input stream is sorted by start, but intervals within a stream may overlap. Treat intervals that touch, such as [1, 3] and [3, 5], as overlapping and merge them.

Use a k-way merge with a min-heap rather than concatenating all streams and sorting them globally.

Formal Specification

Implement merge_interval_streams(streams), where streams is a list of sorted lists of integer intervals. Return a list of disjoint intervals sorted by start time. Return [] when all streams are empty.

Constraints

0 <= len(streams) <= 10^4
Each stream is sorted by interval start time
The total number of intervals across all streams is at most 10^5
-10^9 <= start <= end <= 10^9
Intervals that touch are considered overlapping

Function Signature

def merge_interval_streams(streams):

Your question is Merge Intervals for Multiple Streams. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem