| """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 |
|
|
