Finding number of concurrent events given start and end times
algorithm, computational-geometry, data-structures, language-agnostic
Solution
You're looking for an interval tree.
- Construction: `O(n log n)`, where `n` is the number of intervals
- Query: `O(m+log n)`, where `m` is the number of query results and `n` is the number of intervals
- Space: `O(n)`
Problem
I have a massive (~109) set of events characterized by a start and end time. Given a time, I want to find how many on those events were ongoing at that time. What sort of data structure would be helpful in this situation? The operations I need to be fast are: - Inserting new events, e.g., `{start: 100000 milliseconds, end: 100010 milliseconds}`. - Querying the number of concurrent events at a given time. Update: Someone put a computational geometry flag on this, so I figure I should rephrase this in terms of computational geometry. I have a set of 1-dimensional intervals and I want to calculate how many of those intervals intersect with a given point. Insertion of new intervals must be fast.