地點最近的學生儘可能

-2

你是負責其中有n席位的單行，編號爲0通過n-1 白天學生進入和離開考試教室一個教室。爲了儘量減少作弊，你的任務是有效地安置所有新來的學生。地點最近的學生儘可能

你給出2種類型的查詢：add_student(student_id) -> seat index和remove_student(student_id) -> void

用於安置學生的規則如下：

座椅必須處於未被佔用
最接近的學生必須是儘可能遠的地方
關係可以通過選擇編號最低的座位來解決。

我的方法是使用哈希表，考慮到我們必須爲每個學生分配座位索引，我們可以使用哈希函數進行分配。這種方法是否正確？

如果散列表是正確的方法，那麼對於'最近的學生必須儘可能遠'，我應該如何設計高效的散列函數？

有沒有更好的方法來解決這個問題？

來源

2017-08-17 Jiraya

如果您問是否可以使用散列表存儲與唯一鍵相關聯的值，那麼是的。是的你可以。 – David

這對我來說似乎是一個有趣的問題，所以這裏給出了一些思路後提出的算法。

所以如問題所述，它只是從1到n編號的單行。

我在想這個問題的貪婪方法。

所以在這裏如何去。

人未來第一將以1.
人編輯第二將在第n就座就座，因爲這將創建它們之間的最遠距離。
現在我們開始保留子集，所以我們有一個子集（1，n）。
現在當第三個人進來時，他坐在第一個子集中間，即（1 + n）/ 2。在此之後，我們將有兩個子集 - （1，n/2）和（n/2，n）。
現在當第四個人到達時，他可以坐在（1，n/2）和（n/2，n）的中間。

而且這個流程將繼續。當一個人離開座位走出類

現在假設，那麼，我們的子集範圍將發生變化，然後下一個進來的人時，便計算出一套新的子集爲他的。

希望這會有所幫助。對於這種方法，我認爲一個大小爲n的數組也可以很好地工作。

來源

2017-08-17 17:26:22 zenwraight

更新：此解決方案不起作用，因爲學生可以離開並打開空隙。

所以這裏是我想出的解決方案。我會創建一個初始位置數組。因此，新來的學生的位置只是位置[current_number_of_students-1]。

創建數組是棘手的部分。

def position(number_of_chairs) 
    # handle edge cases 
    return [] if number_of_chairs.nil? || number_of_chairs <= 0 
    return [0] if number_of_chairs == 1 

    # initialize with first chair and the last chair 
    @position = [0, number_of_chairs - 1] 

    # We want to start adding the middle of row segments 
    # but in the correct order. 
    # The first segment is going to be the entire row 
    @segments = [0, number_of_chairs - 1] 

    while [email protected]? 
    current_segment = @segments.shift 
    mid = (current_segment[0] + current_segment[1])/2 
    if (mid > current_segment[0] && mid < current_segment[1]) 
     @position << mid 
     # add the bottom half to the queue 
     @segments.push([current_segment[0], mid]) 
     # add the top half to the queue 
     @segments.push([mid, current_segment[1]]) 
    end 
    end 

    @position 
end

來源

2017-10-19 04:38:37 David

地點最近的學生儘可能

回答

相關問題