# 5.4. Maximum Non-overlapping Intervals

• Problem
  • Let A = \{a_1, a_2, ..., a_n\} be a set of n activities, where a_i has start time s_i and finish times f_i (0 \leq s_i < f_i < \infty ).
  • if selected, activity a_i takes place during the time interval [s_i, f_i).
  • Two activities a_i, a_j are called compatible if the time intervals [s_i, f_i) and [s_j, f_j) do not overlap.
  • Now, select a largest set S of mutually compatible activities. (We assume that the activities are given in such a way that f_1 \leq f_2 ... \leq f_{n-1} \leq f_n)
• Example

A = \{a_1, ..., a_n\} with a_i = [s_i, f_i) for 0 \leq s_i <f_i < \infty

• Possible strategies for choosing activities

  • Longest one first
  • Shortest one first
  • Earliest start first
  • Earliest finish first

• Correctness of “Earliest-finish-first”-based algorithm

  • 귀류법 (Proof by contradiction)
  • Assertion 1 : For any set A of n activities, there always exists an optimal solution S that contains a_1 with the earliest finish time.
  • Assertion 2 : If S is an optimal solution for A containing a_1, S^* = S \ \{a_1\} is an optimal solution for A^* = \{a_i \in A | s_i \geq f_1\}
    • Selecting a_1 reduces the problem to finding an optimal solution for activities not overlapping with a_1.

  A = \{a_1, ..., a_n\} with a_i = [s_i, f_i) for 0 \leq s_i <f_i < \infty

• Greedy algorithm

  • Input: A = \{a_1, ..., a_n\} with a_i = [s_i, f_i) for 0 \leq s_i < f_i <\infty
    1. Sort the activities so that f_1 \leq f_2 \leq ... \leq f_n
    2. S = \{a_1\}
    3. k=1;
    4. for j=2 to n
    5. ` if (s_j \geq f_k)
    6. `` S = S \cup \{a_j\}
    7. `` k=j
    8. return S; → O(n \log n + n) = O(n \log n) time