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 greedy

Non-overlapping Intervals

Problem (restated)

Given intervals, return the minimum number of intervals to remove so the rest are non-overlapping. Endpoints may touch (end == next.start is fine).

Intuition

Maximizing kept intervals is classic activity selection: always keep the interval that finishes earliest so more room remains for later ones. Removals = n - kept.

Approaches

Sort by end + greedy keep

Tested only

Time O(n log n)Space O(1) or O(n)

Idea. Sort by end ascending. Track keptEnd. If next starts before keptEnd, discard it (count +1); else keep it and update keptEnd.

Walkthrough. [[1,2],[2,3],[3,4],[1,3]] → sort by end: [1,2],[1,3],[2,3],[3,4]. Keep [1,2], drop [1,3], keep [2,3], keep [3,4] → 1 removal.

Trade-offs. Sorting by start and always dropping the one with later end is equivalent but slightly more bookkeeping. DP over sorted intervals is correct but slower to code.

Solution

export function eraseOverlapIntervals(intervals: number[][]): number {
  if (!intervals.length) return 0;
  intervals = [...intervals].sort((a, b) => a[1]! - b[1]!);
  let keptEnd = intervals[0]![1]!;
  let removals = 0;
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i]![0]! < keptEnd) removals++;
    else keptEnd = intervals[i]![1]!;
  }
  return removals;
}

export function eraseOverlapIntervals(intervals: number[][]): number {
  if (!intervals.length) return 0;
  intervals = [...intervals].sort((a, b) => a[1]! - b[1]!);
  let keptEnd = intervals[0]![1]!;
  let removals = 0;
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i]![0]! < keptEnd) removals++;
    else keptEnd = intervals[i]![1]!;
  }
  return removals;
}

Template connection

Greedy scheduling on intervals: sort key is end, not start. Contrast with Merge Intervals (sort by start).

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?