O60
Ok ile Balon Patlatma
Teknik Tanım & Görev
2 boyutlu düzlemde yatay çapları [x_baslangic, x_bitis] olan balonlar bulunmaktadır. Dikey olarak fırlatılan bir ok, x konumu balonun aralığındaysa o balonu patlatır. Tek bir okla aynı x koordinatındaki birden fazla balon patlatılabilir. Tüm balonları patlatmak için gereken EN AZ ok sayısını bulunuz.
Fonksiyon İmzası (Python)
min_ok_sayisi(noktalar: list[list[int]]) -> intGirdi ve Çıktı Sözleşmesi
Çıktı Kuralı:Minimum ok sayısı (tam sayı).
Sistem Kısıtları (Constraints)
1 <= noktalar.length <= 10^5
-2^31 <= x_baslangic < x_bitis <= 2^31 - 1Örnek Yürütme Analizi
noktalar = [[10, 16], [2, 8], [1, 6], [7, 12]]
x = 6 oku [2, 8] ve [1, 6]'yı patlatır.
x = 11 oku [10, 16] ve [7, 12]'yi patlatır.
cevap: 2 okÖrnek Test Senaryoları (3)
Örnek 1
Girdi:
[[[10,16],[2,8],[1,6],[7,12]]]Beklenen Çıktı:
2Örnek 2: Ayrık Balonlar
Girdi:
[[[1,2],[3,4],[5,6],[7,8]]]Beklenen Çıktı:
4Örnek 3: Uç Uca Bitişik
Girdi:
[[[1,2],[2,3],[3,4],[4,5]]]Beklenen Çıktı:
2