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.