0

できる限り明確にします。

開始と終了の2回のイベントがあります。(時間は24時間形式です)たとえば、このイベントは8で始まり、12で終わります。

このイベントで、私は彼らの仕事のスケジュールを持つ人のリストを持っています。次に例を示します。

  • 人1:8:00から10:00まで
  • 2人目:10:00〜12:00
  • 人3:6:00〜15:00
  • 4人目:8:00〜9:00
  • 5人目:9時30分から12時まで

さて、イベント全体を通して、少なくとも何人の人がいるのかを知る必要があります。

私の場合、2になります。理由は次のとおりです。

  • 人1と人2は互いに補完し合う
  • 人3は常に存在します
  • 人物4と5の間には、9:00から9:30の間にあえぎがあります。そのため、この間、人物4と5の間には誰もいません。

私がこれを時間で説明すると:

  • 8:00から9:00まで:人1、3、4
  • 9:00から9:30まで:人1、3
  • 9時30分から10時まで:人1、3、5
  • 10:00から12:00まで:人2、3、5

ほとんどの場合、イベントは3人で行われますが、2人の場合は最低です。

アルゴリズムを使用してこの番号を取得するにはどうすればよいですか。これでは気になりません。

時間を分単位で変換し(分を下回らない)、イベント時間の範囲(8*60から12*60)を設定し、各人のプレゼンスを新しい範囲として追加してからカウントすることを考えました。 1分ごとに、スライスがいくつありますか(1スライス= 1人)。しかし、これは効率的ではないと感じています。スライスを4 * 60分間カウントする必要があるためです:/(8-> 12から)。

どうしますか?

4

5 に答える 5

2

個人番号の開始時刻と終了時刻を取得し、それらにi名前を付けます。s_ie_i

これらすべてをリストに入れてくださいtimes。次に、次の手順を実行します。

# start_time contains the start time of the event
# end_time contains the start time of the event
sort(times) # When doing this sort, make sure that if a s_i
            # is at the same time as a e_j, put the s_i first.

current_number = number of people who're there at start_time
remove all times that match start_time from times

minimum_number = current_number

for time in times:
    if time is an s_i: current_number += 1

    if time is an e_i:
        current_number -= 1
        if current_number < minimum_number and time < end_time:
            minimum_number = current_number

このための実行時間は次のとおりです。

n人数にしましょう。

O(n lg n)並べ替える時間しかないので、並べ替えに時間を費やし2nます。

それから私たちはO(n)時間を繰り返し、絶え間ない仕事をします。

全体的に、O(n lg n)。この実行時間は、それがまたがる時間間隔の長さに完全に依存せず、あなたが扱っている人の数にのみ依存することに注意してください。

これは、スイープラインアルゴリズムの形式です。私たちは時代を一掃し、関心のあるポイント(s_iおよびe_is。)でのみ停止します。

s_i同点の場合にsの前にsを並べ替える理由e_jは、次のとおりです。

そうでない場合は、2人の人がいると想像してください。ボブは8〜10歳、アリスは10〜12歳です。その場合、注意深くソートしないと、次の時間のリストが表示される可能性があります。

times = [(s_Bob, 8), (e_Bob, 10), (s_Alice, 10), (e_Alice, 12)]

このように並べ替えると、ボブが10時に出発した後、人が残っていないように見えます。ただし、アリスは同時に到着するため、そこにいます。したがって、これを防ぐために、同点の場合は、開始時刻が終了時刻より前になるように並べ替えます。

times = [(s_Bob, 8), (s_Alice, 10), (e_Bob, 10), (e_Alice, 12)]
于 2012-08-10T12:18:18.480 に答える
0

簡単な答え、おそらく誰かが仕事を開始/終了するたびに人数を更新しますか?

たとえば、t0で、誰がそこにいるかを知るように設定します。次の1分ごと、またはそれ以上の場合、すべての休暇/入国日(ソート済み)について、現在の人数の新しい数に注意してください。

于 2012-08-10T12:15:27.243 に答える
0

イベントにあまり多くの人がいない場合は、次のようなことをすることができます

minimum -> infinity
for each person in persons do:
    intersections -> 0
    for each other person in persons do:
        if other person start time <= person start time
            if other person end time >= person start time
                intersections++
        else if other person start time < person end time
            intersections++
    if intersections < minimum
        minimum = intersections
于 2012-08-10T12:26:38.587 に答える
0

hauronの答えは、私がこのソリューションを作成するのに役立ちました。

言語タグがないため、これが疑似コードです。

開始時刻の並べ替えられたリストと終了時刻の並べ替えられたリストを持っている
現在の人のカウンターをゼロで開始する
また、正の無限大の最小の人のカウンターを持っている最新の時間をイベントの最初の時間として持つ

リストを一緒に調べて、最初の開始時間と最初の終了時間のどちらか早い方を選びます

開始時刻が早い場合は、カウンターをインクリメントして最初の開始時刻を削除します。そうでない場合は、終了時刻が早い場合は、カウンターをデクリメントして最初の終了時刻を削除します。

使用したばかりの時間が直近の時刻と同じでない場合は、最小人数カウンターを確認します(たとえば、3人が同時に入る場合は、3人全員を処理するまで最小人数カウンターを更新するのを待ちます)現在の人数が少ない場合最小人数よりも最小人数を現在の人数に設定

最新の時刻を更新する
両方のリストが空になるまで繰り返します

最小人数カウンターはあなたの答えを持っている必要があります

于 2012-08-10T12:31:58.790 に答える
0

アルゴリズムは次のように設計する必要があると思います。

  • 8:00から:人1、3、4
  • 9:00から:人1、3
  • 9時30分から:人1、3、5
  • 10:00から:人2、3、5

最初にイベントの開始時刻と終了時刻をセットに追加 します。次に、メンバーを繰り返し処理して、開始時刻と終了時刻のセットを作成します(セットは重複を防ぎます)。次に、セット内のアイテムを繰り返し処理し、各メンバーをセット内の各要素と照合して、開始時刻が> =で、終了時刻が>であるかどうかを確認し、セット内のアイテムを確認します。特定の時間の人数を追跡するための内部反復のカウンターを用意し、特定の時間の最小人数を追跡する両方の反復の外部の変数を用意します。擬似コードの場合:

var set : set
var event_start : time = 8:00
var event_end : time = 12:00
set.add(event_start)
foreach(person in people)
    set.add(person.start)
    set.add(person.end)
var min : int = people.size
var time_of_min : time
foreach time in set
    var num_people : int = 0
    foreach person in people
        if person.start >= time && person.end > time
            num_people++
    if num_people < min
        min = num_people
        time_of_min = time
// Handle the special case of the ending time
var num_people_at_end : int = 0
foreach person in people
    if person.end == event_end
        num_people_at_end++
if num_people_at_end < min
    min = num_people_at_end
    time_of_min = event_end
于 2012-08-10T12:32:26.563 に答える