Sıralı aralıklardan bir aralık kes
Görev tanımı
Problem
Bir sayı kümesi (set), her biri a'dan b'ye kadar, b hariç, her sayıyı kapsayan yarı açık [a, b) aralıklarından oluşan sıralı ve ayrık bir liste olarak saklanıyor. Bir aralık daha, cut = [lo, hi), verildiğinde, onun kapsadığı her sayıyı kümeden sil ve kalanı yine sıralı ve ayrık aralıklardan oluşan bir liste olarak döndür.
Örnekler
Input: spans = [[0, 2], [3, 4], [5, 7]], cut = [1, 6]
Output: [[0, 1], [6, 7]]
Neden: kesim ilk aralığı kırpar, ikincisini yutar, üçüncüsünü kırpar
Input: spans = [[0, 5]], cut = [2, 3]
Output: [[0, 2], [3, 5]]
Neden: tek bir aralığın içindeki kesim onu ikiye böler
Input: spans = [[-5, -4], [-3, -2], [1, 2], [3, 5], [8, 9]], cut = [-1, 4]
Output: [[-5, -4], [-3, -2], [4, 5], [8, 9]]
Neden: edge case: tamamen kesimin dışındaki aralıklar dokunulmadan geçer
İpuçları
0 / 3
Her aralığa tek başına bak. Kesime göre ya tamamen öncesindedir, ya tamamen sonrasındadır ya da onunla örtüşür.
Yarı açık aralıklarla [a, b), [lo, hi)'yı tam olarak b <= lo ya da a >= hi olduğunda ıskalar. Bu aralıklar bütün olarak tutulur.
Örtüşen bir aralık en fazla iki parça bırakabilir: kesimden önce başlıyorsa [a, lo), kesimden sonra bitiyorsa [hi, b). İkisinden hangileri varsa o sırayla çıkar.
- Hedef zaman
- O(n)
- Hedef alan
- O(n)
Kısıtlar
- the spans are sorted and disjoint
Çözüm
Liste zaten sıralı ve ayrık; bu yüzden sırayla tek bir geçiş yeter ve çıktı hiçbir ek iş olmadan sıralı kalır. Her aralık kesimle bir kez karşılaştırılır: örtüşmüyorlarsa kopyalanır, örtüşüyorlarsa yalnız solda ve sağda dışarı taşan kısımlar hayatta kalır. Kesimin tamamen kapsadığı bir aralık hiçbir parça üretmez ve kaybolur; kesimin içine düştüğü bir aralık ise ikisini de üretir, bölme de budur. Yarı açık aralıklar aritmetiği temiz tutar, çünkü hayatta kalan parçalar artı ya da eksi bir olmadan tam olarak lo'da biter ve tam olarak hi'de başlar. Zaman O(n), çıktı en fazla n + 1 aralık tutar.
def cut_span(spans, cut):
lo, hi = cut
out = []
for a, b in spans:
if b <= lo or a >= hi: # no overlap: keep the whole span
out.append([a, b])
continue
if a < lo:
out.append([a, lo]) # the part left of the cut survives
if b > hi:
out.append([hi, b]) # the part right of the cut survives
return out
print(cut_span([[0, 2], [3, 4], [5, 7]], [1, 6])) # -> [[0, 1], [6, 7]]
print(cut_span([[0, 5]], [2, 3])) # -> [[0, 2], [3, 5]]
print(cut_span([[-5, -4], [-3, -2], [1, 2], [3, 5], [8, 9]], [-1, 4])) # -> [[-5, -4], [-3, -2], [4, 5], [8, 9]]Kodda değil de fikirde mi takıldın? Insert Interval bunu anlatıyor.