Maximum Bandwidth (Weighted Interval Overlap)

# Maximum Bandwidth (Weighted Interval Overlap) ## Difficulty Medium ## Tags `array`, `sorting`, `sweep line` ## Problem Statement You have a schedule of TV shows. Each show has a start time, end time, and bandwidth consumption. Find the **maximum total bandwidth** consumed at any single point in time. Multiple shows can run simultaneously, and their bandwidths add up. ## Constraints - 1 ≤ shows.length ≤ 10⁴ - 0 ≤ start < end ≤ 10⁶ - 1 ≤ bandwidth ≤ 1000 - Intervals are half-open: [start, end) — a show ending at time T does not overlap with one starting at time T. ## Signatures ### Python ```python def max_bandwidth(shows: List[Tuple[int) -> int: pass ``` ### Java ```java public class Solution { public int max_bandwidth(Object shows) { return null; } } ``` ### Csharp ```csharp public class Solution { public int max_bandwidth(Object shows) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: int max_bandwidth(Object shows) { } }; ``` ### C ```c int max_bandwidth(Object shows) { } ``` ### Ruby ```ruby def max_bandwidth(shows) end ``` ### Perl ```perl sub max_bandwidth { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def max_bandwidth(shows: Object): Int = { } } ``` ### Haskell ```haskell max_bandwidth :: ... -> ... max_bandwidth args = undefined ``` ### Clojure ```clojure (defn max_bandwidth [shows] ) ``` ### Scheme ```scheme (define (max_bandwidth shows) ) ``` ## Examples ### Example 1 **Input:** ``` shows = [(1, 5, 10), (2, 6, 5)] ``` **Output:** ``` 15 ``` **Explanation:** - Time 1: Show 1 starts → bandwidth = 10 - Time 2: Show 2 starts → bandwidth = 10 + 5 = 15 - Time 5: Show 1 ends → bandwidth = 5 - Time 6: Show 2 ends → bandwidth = 0 - Maximum is 15 (during interval [2, 5)). ### Example 2 **Input:** ``` shows = [(0, 10, 100), (5, 15, 50), (10, 20, 75)] ``` **Output:** ``` 150 ``` **Explanation:** - [0, 5): 100 - [5, 10): 100 + 50 = 150 ← maximum - [10, 15): 50 + 75 = 125 - [15, 20): 75 ### Example 3 **Input:** ``` shows = [(1, 2, 10), (3, 4, 20), (5, 6, 30)] ``` **Output:** ``` 30 ``` **Explanation:** No overlaps, so max is the largest individual bandwidth. ### Example 4 **Input:** ``` shows = [(0, 10, 5), (0, 10, 5), (0, 10, 5)] ``` **Output:** ``` 15 ``` **Explanation:** All three shows run simultaneously for the entire duration. ## Hints 1. Use the **sweep line** algorithm. 2. Convert each show into two events: `(start, +bandwidth)` and `(end, -bandwidth)`. 3. Sort all events by time. For ties, process "end" events before "start" events (for half-open intervals). 4. Iterate through events, maintaining a running sum. Track the maximum. 5. Time complexity: O(N log N) for sorting.