İçeriğe geç

Adayları iki şehir arasında böl

Kolay#greedy#sort-by-difference~20 dk

Görev tanımı

Problem

Bir şirket çift sayıda adayı yerinde mülakatlara uçuruyor ve tam yarısı A ofisine, yarısı B ofisine gitmeli. costs[i] = [a, b], i adayının her ofise uçuş ücretini veriyor. Adayların tam yarısını her ofise gönderen en düşük toplam ücreti döndür.

Örnekler

Input:  costs = [[10, 20], [30, 200], [400, 50], [30, 20]]
Output: 110
Neden: ilk ikisi 10 + 30 ile A'ya, son ikisi 50 + 20 ile B'ye gider
Input:  costs = [[259, 770], [448, 54], [926, 667], [184, 139], [840, 118], [577, 469]]
Output: 1859
Input:  costs = [[5, 5], [7, 7]]
Output: 12
Neden: edge case: iki ofis de aynı tutuyor, yani herhangi bir eşit bölünme optimal

İpuçları

0 / 3

Hedef zaman
O(n log n)
Hedef alan
O(n)

Kısıtlar

  • the number of candidates is even

Kodda değil de fikirde mi takıldın? Sıralama temelleri bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case