File size: 1,796 Bytes
63f6453 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | """Kapalı aralıklar [baş, son] üzerinde işlemler."""
from typing import List, Tuple
Interval = Tuple[int, int]
def validate(iv: Interval) -> None:
if len(iv) != 2:
raise ValueError("aralık iki elemanlı olmalı")
if iv[0] > iv[1]:
raise ValueError(f"geçersiz aralık: {iv}")
def merge(intervals: List[Interval]) -> List[Interval]:
"""Çakışan veya bitişik (ör. [1,3] ve [4,5]) aralıkları birleştirir."""
for iv in intervals:
validate(iv)
result: List[Interval] = []
for start, end in sorted(intervals):
if result and start <= result[-1][1] + 1:
result[-1] = (result[-1][0], max(result[-1][1], end))
else:
result.append((start, end))
return result
def total_length(intervals: List[Interval]) -> int:
"""Birleştirilmiş aralıkların kapsadığı tam sayı adedi."""
return sum(end - start + 1 for start, end in merge(intervals))
def contains(intervals: List[Interval], x: int) -> bool:
lo, hi = 0, len(merged := merge(intervals)) - 1
while lo <= hi:
mid = (lo + hi) // 2
s, e = merged[mid]
if x < s:
hi = mid - 1
elif x > e:
lo = mid + 1
else:
return True
return False
def gaps(intervals: List[Interval], lower: int, upper: int) -> List[Interval]:
"""[lower, upper] içinde hiçbir aralığın kapsamadığı boşluklar."""
if lower > upper:
raise ValueError("lower > upper")
out: List[Interval] = []
cur = lower
for s, e in merge(intervals):
if e < lower or s > upper:
continue
if s > cur:
out.append((cur, s - 1))
cur = max(cur, e + 1)
if cur <= upper:
out.append((cur, upper))
return out
|