Problem: Global GPU Idle Intervals

You are given a set of GPU tasks. Each task is defined by a tuple (start, end, node_id) where:

• start and end are timestamps (e.g., integers, with start < end).
• The task runs on a single GPU identified by node_id.
• Multiple tasks may overlap in time, potentially on different nodes.

Define the GPU fleet idle time as any time interval during which no tasks are running on any node across the entire fleet (i.e., the total number of active tasks is 0).

Part 1: Batch Processing

Given an unsorted list of tasks, return all maximal idle time intervals as a list of disjoint intervals (idle_start, idle_end).

Clarifications/Assumptions:

• You should infer the overall time range from the tasks themselves. Consider idle gaps only between the earliest task start and the latest task end.
• If tasks touch (e.g., one ends at t and another starts at t), there is no idle time at t.

Part 2: Streaming Processing

Now, tasks arrive one at a time in a stream. Design an efficient approach and data structure that supports:

• addTask(start, end, node_id): Adds a new task to the system.
• getIdleIntervals(): Returns the current set of maximal idle intervals based on all tasks seen so far.

Discuss the expected time and space complexity per operation for your proposed solution. You may assume timestamps are integers, and tasks may arrive out of order.