一連の時間間隔を指定して、オーバーラップの最大数を見つける方法。与えられた問題を時間計算量 O(n log n ) または O(n) で解決するアルゴリズムはありますか??
例 : (6:00-9:30),(9:00-12:30),(10:00-10:30), (12:00-14:30), (11:00-13:30) ).答えは 3
一連の時間間隔を指定して、オーバーラップの最大数を見つける方法。与えられた問題を時間計算量 O(n log n ) または O(n) で解決するアルゴリズムはありますか??
例 : (6:00-9:30),(9:00-12:30),(10:00-10:30), (12:00-14:30), (11:00-13:30) ).答えは 3
クイックソート -- 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)