Formatted question description: https://leetcode.ca/all/352.html
Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals. For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be: [1, 1] [1, 1], [3, 3] [1, 1], [3, 3], [7, 7] [1, 3], [7, 7] [1, 3], [6, 7] Follow up: What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size? @tag-array @tag-interval
To get previous range last index, and next range first index. Then compare and decide if merge or not.
Integer l = tree.lowerKey(val); // @note: Returns the greatest key strictly less than the given key Integer h = tree.higherKey(val); // @note: Returns the least key strictly greater than the given key
Interval start/end check
Every time a new number val comes in, a new interval [val, val] is generated, and an empty interval array res is created, and a variable cur is used to store the position of the new interval.
Traverse the existing interval array intervals, for each traversed current interval interval,
- If the end position of the interval to be added plus 1 is smaller than the start position of the current interval, indicating that the two are not connected, add the current interval to res.
- Otherwise, when the start position of the interval to be added is greater than the end position of the current position plus 1, it means that there is no intersection between the two, and the current interval can be added to res,
- But at this time, cur should be incremented by 1 because the position to be added to the interval is behind the current interval.
- Otherwise, the two will overlap and need to be merged,
- At this time, use the smaller of the two starting positions to update the starting position of the interval to be added,
- In the same way, use the larger of the two end positions to update the end position of the interval to be added.
Finally, the interval to be added is placed at the cur position in res, and then res is assigned to intervals
Follow up: What if there are lots of merges and the number of disjoint intervals are small compared to the data stream’s size?
- lots of merges
->add() cannot be too costy
- the number of disjoint intervals are small
->get() can be costy
to reduce cost of add(), use
O(logn) for insertion of points (no merge), and maintain order
get will have to calculate the disjoint intervals on the fly (basically
lazy loading, do a merge on