Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumintervals

Interval List Intersections

Problem (yeniden ifade)

İki kapalı aralık listesi; her liste kendi içinde ikili ayrık ve sıralı. İki listenin kesişim aralıklarını döndür.

Sezgi

İki işaretçi. A[i] ve B[j] kesişimi, boş değilse [max(başlangıçlar), min(bitişler)]. Bitişi önce gelen aralığı ilerlet.

Yaklaşımlar

Sıralı listelerin iki işaretçi ile birleştirmesi

Tested only

Time O(m + n)Space O(1) ekstra

Fikir. Sıralı + ayrık yapı, örtüşmeleri kaçırmadan doğrusal taramayı garanti eder.

Adım adım. [[0,2],[5,10],[13,23],[24,25]] ∩ [[1,5],[8,12],[15,24],[25,26]] → [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]].

Trade-off’lar. Her aralık için ikili arama, her iki liste de uzunken daha kötü.

Solution

export function intervalIntersection(
  firstList: number[][],
  secondList: number[][],
): number[][] {
  const res: number[][] = [];
  let i = 0, j = 0;
  while (i < firstList.length && j < secondList.length) {
    const lo = Math.max(firstList[i]![0]!, secondList[j]![0]!);
    const hi = Math.min(firstList[i]![1]!, secondList[j]![1]!);
    if (lo <= hi) res.push([lo, hi]);
    if (firstList[i]![1]! < secondList[j]![1]!) i++;
    else j++;
  }
  return res;
}

export function intervalIntersection(
  firstList: number[][],
  secondList: number[][],
): number[][] {
  const res: number[][] = [];
  let i = 0, j = 0;
  while (i < firstList.length && j < secondList.length) {
    const lo = Math.max(firstList[i]![0]!, secondList[j]![0]!);
    const hi = Math.min(firstList[i]![1]!, secondList[j]![1]!);
    if (lo <= hi) res.push([lo, hi]);
    if (firstList[i]![1]! < secondList[j]![1]!) i++;
    else j++;
  }
  return res;
}

Şablon bağlantısı

Aralık iki işaretçi taraması.

Yansıma

Hangi kalıp bunu 90 saniyede ele verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozar?