Weighted Interval Schedule Maximization Problem (ISMP)

In Weighted Interval Scheduling, each interval has an associated weight. The goal is to maximize the weights of the accepted (and not interrupted) intervals.

Parameters

$n$ : number of tasks (intervals)
$k$ : number of machines (resources)

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 4 of 4 algorithms


$O(n^3)$ Dynamic Programming	1953	$O(n^3)$	$O(n^2)$
$O(n^2)$ Dynamic Programming	1953	$O(n^2)$	$O(n)$
$O(n\log n)$ Dynamic Programming	1953	$O(n \log n)$	$O(n)$
Brute force algorithm	1940	$O(2^n)$	$O(n)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms