MaxIntervalCover.js

MaxIntervalCover is a lightweight JavaScript library for solving the maximum interval coverage problem.
It finds the subset of intervals that maximizes the total covered length while ensuring no overlaps,
with an additional tie-break rule preferring fewer intervals when lengths are equal.

Features

• Handles both half-open [a, b) and closed [a, b] intervals
• Accepts input as {a, b} objects or [a, b] arrays
• Drops zero-length and invalid intervals automatically
• Finds an optimal non-overlapping subset of intervals:
  • Maximizes the total covered length
  • On ties, prefers fewer intervals
• Efficient O(n log n) algorithm based on dynamic programming and binary search
• Works with fractional and very large interval endpoints

Installation

Install via npm:

npm install maxintervalcover

Or with yarn:

yarn add maxintervalcover

Alternatively, download or clone the repository:

git clone https://github.com/rawify/MaxIntervalCover

Usage

In a Node.js project:

const { MaxIntervalCover } = require("maxintervalcover");

or with ES modules:

import { MaxIntervalCover } from "maxintervalcover";

Basic Example

const intervals = [
  { a: 0, b: 3 },
  { a: 2, b: 5 },
  { a: 6, b: 10 }
];

const result = MaxIntervalCover(intervals, true); // half-open [a,b)
console.log(result);
// -> [ { a: 0, b: 3 }, { a: 6, b: 10 } ]

Array Input Example

const intervals = [[1, 3], [2, 14], [4, 10]];
const result = MaxIntervalCover(intervals);
// -> [ { a: 2, b: 14, idx: 1, weight: 12 } ]

Closed Intervals

const intervals = [[0, 1], [1, 2], [2, 3]];
const result = MaxIntervalCover(intervals, false); // closed [a,b]
console.log(result);
// -> [ { a: 0, b: 1 }, { a: 2, b: 3 } ]

API

MaxIntervalCover(ints, isHalfOpen = true)

Computes the maximum interval coverage.

• ints: Array of intervals in either form:

  • {a: number, b: number}
  • [a, b]

• isHalfOpen: Boolean, default true.

  • true: Intervals are half-open [a, b) → touching intervals allowed
  • false: Intervals are closed [a, b] → touching intervals forbidden

Returns: Array of chosen intervals (subset of input).

Coding Style

Like all my libraries, MaxIntervalCover is written to minimize size after compression with Google Closure Compiler in advanced mode. The code style is optimized to maximize compressibility. If you extend the library, please preserve this style.

Building the library

After cloning the Git repository run:

npm install
npm run build

Run Tests

npm test

Copyright and Licensing

Copyright (c) 2025, Robert Eisele Licensed under the MIT license.