我有一组具有开始和结束时间的事件。我想生成一个数组的时间和事件的数量,当时的值为创建一个图形的变化。到目前为止,我通过开始和结束时间的多次迭代来计算值。还有别的办法吗?
。
Event 1: Jan 1 to Jan 10
Event 2: Jan 6 to Feb 6
Event 3: jan 8 to Feb 1
我应该得到一个像
这样的数组Jan 1: 1
Jan 6: 2
Jan 8: 3
Jan 11: 2
Feb 2: 1
Feb 7: 0
创建一个包含所有开始和结束时间的数组,以及事件是在此日期开始(1)还是结束(-1)的信息:
[(Jan 1 , 1), (Jan 10, -1), (Jan 6, 1), (Feb 6, -1), (Jan 8, 1), (Feb 1, -1)]
按日期排序:
[(Jan 1 , 1), (Jan 6, 1), (Jan 8, 1), (Jan 10, -1), (Feb 1, -1), (Feb 6, -1)]
遍历数组,保留一个计数器,并酌情在数组中添加日期。您可能希望将同一日期的不同出现合并到单个条目中。
(这不是O(n),但我认为目标是比原来的O(n²)更好)
如果您将事件作为排序列表(最早日期优先),则
running_count = 0
list_of_end_dates = [];
vector_of_date_events_pairs = [];
For Each item in the events collection {
running_count += 1
while(queue.tail < item.end_date) {
queue.pop_back()
running_count -= 1
}
vector_of_date_events_pairs.push(item.start_date, running_count)
list_of_end_dates.push_front(item.end_date)
}