所有的时间间隔重叠的最大无 [英] Maximum no of overlaps of all time intervals

问题描述

给定一组时间间隔，如何找到找到最大不重叠。有没有什么算法，有时间复杂度为O解决给定的问题（N log n）的或为O（n）??

Given a set of time intervals , how to find the find the maximum no of overlaps . Is there any algorithm which solves the given problem with time complexity O(n log n ) or O(n)??

例如：（6：00-9：30），（9：00-12：30），（10：00-10：30），（12：00-14：30），（11：00- 13:30）.The答案是3

example : (6:00-9:30),(9:00-12:30),(10:00-10:30), (12:00-14:30), (11:00-13:30).The answer is 3

推荐答案

使用排序快速排序的价值观 - O（nlogn）时间

Sort the values using quick sort -- O(nlogn) time.

 6:00(+)
 9:30(-)
 9:00(+)
12:30(-)
10:00(+)
10:30(-)
12:14:30(Dude wut?) --> Im going to assume you meant 12:00(+) ,14:30(-)
11:00(+)
13:30(-)

变为

 6:00(+)
 9:00(+)
 9:30(-)
10:00(+)
10:30(-)
11:00(+)
12:00(+)
12:30(-)
13:30(-)
14:30(-)

遍历列表递增，每加和递减，每负，记录发现的最大值。这需要 O（N）时间

总时间 O（nlogn + N）= O（nlogn）

这篇关于所有的时间间隔重叠的最大无的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！