/interval-scheduling

Greedy Algorithm to find the maximum number of mutually compatible jobs

Primary LanguageJava

Interval Scheduling

Greedy Algorithm to find the maximum number of mutually compatible jobs

Problem Statement

  • Job j starts at s(j) and finishes at f(j)
  • 2 jobs are compatible if they do not overlap (2nd job starts after or at the same time as the 1st one finishes)
  • Goal: find the maximum number of mutually compatible jobs
  • Example: 8 jobs {a, b, c, d, e, f, g, h}

Optimal = {b, e, h}

Algorithm

Consider jobs in ascending order of finish time f(j)

Sorted Jobs

Pseudocode

Runtime

Sorting O(n log(n)) + for-loop Θ(n)
O(n log(n))

References