Non-overlapping Intervals

[jsartisan]

Info

difficulty: medium
title: Non-overlapping Intervals
type: question
template: typescript
tags: javascript, blind75, intervals, greedy

Question

Given an array of intervals where intervals[i] = [start_i, end_i], find the minimum number of intervals to remove to make the remaining intervals non-overlapping.

Rules:

• Intervals with common endpoints are considered non-overlapping
• Must remove minimum number of intervals
• Intervals overlap if they share any points except endpoints

Constraints:

• 1 ≤ intervals.length ≤ 1000
• intervals[i].length == 2
• -50000 ≤ start < end ≤ 50000

Examples:

// Example 1:
console.log(eraseOverlapIntervals([[1,2],[2,4],[1,4]]));
// Output: 1
// Explanation: Remove [1,4] to make non-overlapping

// Example 2:
console.log(eraseOverlapIntervals([[1,2],[2,4]]));
// Output: 0
// Explanation: Already non-overlapping

Template

index.ts

export function eraseOverlapIntervals(intervals: number[][]): number {

}

index.test.ts

import { eraseOverlapIntervals } from './index';

describe('eraseOverlapIntervals', () => {
  test('Example 1: One removal needed', () => {
    expect(eraseOverlapIntervals([[1,2],[2,4],[1,4]])).toBe(1);
  });

  test('Example 2: No removal needed', () => {
    expect(eraseOverlapIntervals([[1,2],[2,4]])).toBe(0);
  });

  test('Single interval', () => {
    expect(eraseOverlapIntervals([[1,2]])).toBe(0);
  });

  test('All overlapping', () => {
    expect(eraseOverlapIntervals([[1,2],[1,2],[1,2]])).toBe(2);
  });

  test('Multiple overlaps', () => {
    expect(eraseOverlapIntervals([[1,4],[2,3],[3,4],[1,2]])).toBe(1);
  });

  test('No overlaps', () => {
    expect(eraseOverlapIntervals([[1,2],[3,4],[5,6]])).toBe(0);
  });

  test('Complex overlapping', () => {
    expect(eraseOverlapIntervals([[1,5],[2,3],[3,4],[4,5]])).toBe(1);
  });

  test('Negative intervals', () => {
    expect(eraseOverlapIntervals([[-3,-2],[-2,-1],[-1,0]])).toBe(0);
  });

  test('Mixed positive and negative', () => {
    expect(eraseOverlapIntervals([[-1,1],[0,2],[1,3],[2,4]])).toBe(1);
  });

  test('Large intervals', () => {
    expect(eraseOverlapIntervals([[1,100],[2,3],[4,5]])).toBe(1);
  });
});

[github-actions[bot]]

316 - Pull Request updated.