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

Mediumtopological-sort

Parallel Courses

Problem (yeniden ifade)

n ders (1..n), önkoşullar [prev, next]. Her dönem önkoşulu sağlanmış istediğin kadar ders alabilirsin. Hepsini bitirmek için min dönem, imkânsızsa -1.

Sezgi

Katmanlı Kahn: her BFS katmanı bir dönem. Tüm dersler alınmadıysa döngü → -1.

Yaklaşımlar

Dönem katmanlarıyla Kahn

Doğrulanmadı

Zaman O(n + e)Alan O(n + e)

Fikir. indegree 0 ile başla; kuyruğun tüm seviyesini işle, sonra dönemi artır.

Yürüyüş. n=3, [[1,3],[2,3]] → 2 dönem.

Trade-off. Course Schedule ile aynı graf; cevap DAG’deki en uzun yol uzunluğu (+1).

Çözüm

export function minimumSemesters(n: number, relations: number[][]): number {
  const g: number[][] = Array.from({ length: n + 1 }, () => []);
  const indeg = Array(n + 1).fill(0);
  for (const e of relations) {
    g[e[0]!]!.push(e[1]!);
    indeg[e[1]!]!++;
  }
  let q: number[] = [];
  for (let i = 1; i <= n; i++) if (indeg[i] === 0) q.push(i);
  let sem = 0, taken = 0;
  while (q.length) {
    const next: number[] = [];
    for (const u of q) {
      taken++;
      for (const v of g[u]!) {
        if (--indeg[v]! === 0) next.push(v);
      }
    }
    sem++;
    q = next;
  }
  return taken === n ? sem : -1;
}

export function minimumSemesters(n: number, relations: number[][]): number {
  const g: number[][] = Array.from({ length: n + 1 }, () => []);
  const indeg = Array(n + 1).fill(0);
  for (const e of relations) {
    g[e[0]!]!.push(e[1]!);
    indeg[e[1]!]!++;
  }
  let q: number[] = [];
  for (let i = 1; i <= n; i++) if (indeg[i] === 0) q.push(i);
  let sem = 0, taken = 0;
  while (q.length) {
    const next: number[] = [];
    for (const u of q) {
      taken++;
      for (const v of g[u]!) {
        if (--indeg[v]! === 0) next.push(v);
      }
    }
    sem++;
    q = next;
  }
  return taken === n ? sem : -1;
}

Şablon bağlantısı

Seviye sayımıyla topological sort.

Yansıma

Kahn katmanı bir dönem. O turdaki indegree 0 derslerin hepsi paralel. Dönem sayısı katman sayısı.
Döngüde kuyruk erken biter: −1. Kenar yoksa her ders ilk dönemde: 1.
Zincir n ders n dönem. İki bağımsız ders 1 dönem.