---
# System prepended metadata

title: Untitled

---

IntuitionIf we use an array vals with length 1e9 to represent how many events (intervals) covering a time t, each time a new event [start, end) is added, we just need to increase all values in the subarray of vals from index start to end-1 by 1, and then return the max value in val.

A segment tree with lazy tags is often used in this scenario to update scalar data (e.g., max, min, sum, etc.) of a subarray quickly. In this problem, we can use a TreeNode to store the max numbers of intervals in a time range [L, R]. A TreeNode has the following fields:
L and R: the end points of the interval represented by this TreeNode.val: the max number of events at a time included in this range [L, R]lazy: the number of events covering all times in the range. As all numbers that belong to this range will be added by some increment, we don't have to propagate the base increment to every time in the interval, all we need to do is putting the number in this lazy field. We only update val by adding lazy when requested to query the max numbers of intervals in [L, R].left and right: The left and right child nodes of this node, should represent the range [L, M] and [M + 1, R] respectively unless left = right, M = (L + R) / 2 here.AlgorithmEach time adding a new event [start, end), we start from the root node, which represents the time interval [0, C], where C is the largest possible time and equals to 1e9 in this problem, check if [start, end - 1] has any intersection with current range [L, R] ([0, C] for the root node), and update those nodes recursively:
If L > end - 1 or R < start, no elements in [start, end - 1] are included in current node, just return.If start <= L and R >= end - 1, the range represented by this node is completely contained in [start, end - 1]. All elements in the range will be added by 1, so we just need to increase its lazy and val by 1 and stop.Otherwise, only partial numbers in this range are coverd by [start, end). We just go to the two child nodes and repeat the checking steps above to update them. After updating data in child nodes, don't forget to update val of our current node by lazy + max(left.val, right.val), because the max numbers must come from either left or right half of the range, plus the number shared by all elements in the interval, which is stored in lazy.The val of the root node is exactly the answer we want.ImplementationAs we discussed before, the input endpoints are sparse. We don't have to create TreeNode for all intervals in the beginning. We can create a node dynamically when needed. Besides, we don't need to define a TreeNode class, instead, we can represent them by hashmap with unique idxs as keys and specify values at key 2 * idx and 2 * idx + 1 as its left and right child nodes for any idx > 0.