Solve interval, grid-fill, and heap tasks

You are asked to solve the following algorithmic problems. ## Problem 1: Concurrent users from online intervals You are given `n` inclusive time intervals `intervals[i] = [start_i, end_i]`, each representing one user being online from `start_i` through `end_i` (integer timestamps). Return the online user count over time as a list of **disjoint** segments where the count is constant: `[t0, t1, c]` meaning for every integer time `t` with `t0 <= t <= t1`, exactly `c` users are online. ### Input - `intervals`: list of `n` pairs `[start, end]` with `start <= end` ### Output - `segments`: list of disjoint segments `[L, R, count]` sorted by time, covering exactly the union of times present in the input. ### Constraints (choose a reasonable approach) - `1 <= n <= 2e5` - Timestamps can be large (e.g., up to `1e9`), so avoid building an array over the raw time range. --- ## Problem 2: Fill a grid with vegetables so each type is connected You are given a grid with `R` rows and `C` columns. You are also given counts of vegetable types, e.g. `{'A': 4, 'B': 8, 'C': 3, ...}`, where the total count equals `R*C`. Fill the grid with these letters such that: - Every cell contains exactly one vegetable letter. - For each letter, all of its cells form a **single 4-directionally connected component** (up/down/left/right). ### Output Return any valid `R x C` grid, or report that it’s impossible. ### Follow-up How should your solution behave if some vegetable counts are `0`, or if `R*C = 0` (empty grid)? --- ## Problem 3: Support retrieving both min and max efficiently Design a data structure supporting these operations on a multiset of integers: - `insert(x)` - `getMin()` - `getMax()` - `popMin()` (remove and return current minimum) - `popMax()` (remove and return current maximum) ### Requirements - Target better than sorting the whole set on every operation. - Discuss time complexity. - Discuss when a counting/bucket approach could be better, and when it is not appropriate.