Question

Consider the following variation on the Activity Selection Problem.You have a resource that may be used for activities 24 hours a day,ever day.Activities repeat that may be used for activities repeat on a daily basis. As in the original problem, each activity has a start time and as end time.If an activity is selected, it will exclusively use the resource during the duration between the start and end time(i.e., no other activity may be scheduled during this time). Note that jobs can begin before midnight and end midnight; this situation differentiates it from the original Activity Selection Problem.
Given a list of n activities, your goal is to accept as many activities as possible for a daily scheduled of activities(i.e., every day the schedule of activities will be identical). Provide an algorithm for activity selection with running time polynomial in n. You may assume for simplicity that no two jobs have same start or end times.
An Example: Consider the following four activities, where each activity is specified by(start-time, end-time) pair(using 24-time).
(18:00,6:00),(21:00,4:00),(3:00,14:00),(13:00,19:00).
The optimal solution would be to pick the two jobs(21:00,4:00) and (13:00,19:00), which can be scheduled without overlapping.

Answer 1

An activity-selection is the problem of scheduling a resource among several competing activity.

Statement: Given a set S of n activities with and start time, Si and fi, finish time of an ith activity. Find the maximum size set of mutually compatible activities.

Compatible Activities
Activities i and j are compatible if the half-open internal [si, fi) and [sj, fj) do not overlap, that is, i and j are compatible if si = fj and sj = fi
Greedy Algorithm for Selection Problem

I. Sort the input activities by increasing finishing time.
f1 = f2 = . . . = fn

II Call GREEDY-ACTIVITY-SELECTOR (Sif)

n = length [s]
A={i}
j = 1
FOR i = 2 to n
do if si = fj
then A= AU{i}
j = i
Return A

Operation of the algorithm
Let 11 activities are given S = {p, q, r, s, t, u, v, w, x, y, z} start and finished times for proposed activities are (1, 4), (3, 5), (0, 6), 5, 7), (3, 8), 5, 9), (6, 10), (8, 11), (8, 12), (2, 13) and (12, 14).

A = {p} Initialization at line 2
A = {p, s} line 6 - 1st iteration of FOR - loop
A = {p, s, w} line 6 -2nd iteration of FOR - loop
A = {p, s, w, z} line 6 - 3rd iteration of FOR-loop
Out of the FOR-loop and Return A = {p, s, w, z}

Analysis
Part I requires O(nlgn) time (use merge of heap sort).
Part II requires Theta(n) time assuming that activities were already sorted in part I by their finish time.

CORRECTNESS
Note that Greedy algorithm do not always produce optimal solutions but GREEDY-ACTIVITY-SELECTOR does.

Theorem: Algorithm GREED-ACTIVITY-SELECTOR produces solution of maximum size for the activity-selection problem.

Proof Idea: Show the activity problem satisfied
I. Greedy choice property.
II. Optimal substructure property

Proof:
I. Let S = {1, 2, . . . , n} be the set of activities. Since activities are in order by finish time. It implies that activity 1 has the earliest finish time.
Suppose, A is a subset of S is an optimal solution and let activities in A are ordered by finish time. Suppose, the first activity in A is k.
If k = 1, then A begins with greedy choice and we are done (or to be very precise, there is nothing to proof here).
If k not=1, we want to show that there is another solution B that begins with greedy choice, activity 1.
Let B = A - {k} U {1}. Because f1 =< fk, the activities in B are disjoint and since B has same number of activities as A, i.e., |A| = |B|, B is also optimal.

II. Once the greedy choice is made, the problem reduces to finding an optimal solution for the problem. If A is an optimal solution to the original problem S, then A` = A - {1} is an optimal solution to the activity-selection problem S` = {i in S: Si >= fi}.
why?

If we could find a solution B` to S` with more activities then A`, adding 1 to B` would yield a solution B to S with more activities than A, there by contradicting the optimality.

Dynamic-Programming Algorithm for the Activity-Selection Problem

Problem: Given a set of activities to among lecture halls. Schedule all the activities using minimal lecture halls.
In order to determine which activity should use which lecture hall, the algorithm uses the GREEDY-ACTIVITY-SELECTOR to calculate the activities in the first lecture hall. If there are some activities yet to be scheduled, a new lecture hall is selected and GREEDY-ACTIVITY-SELECTOR is called again. This continues until all activities have been scheduled.

LECTURE-HALL-ASSIGNMENT (s,f)

n = length [s)
FOR i = 1 to n
DO HALL [i] = NIL
k = 1
WHILE (Not empty (s))
Do HALL [k] = GREEDY-ACTIVITY-SELECTOR (s, t, n)
k = k + 1
RETURN HALL

Following changes can be made in the GREEDY-ACTIVITY-SELECTOR (s, f) (CLR).

j = first (s)
A = i
FOR i = j + 1 to n
DO IF s(i) not= "-"
THEN IF

GREED-ACTIVITY-SELECTOR (s,f,n)

j = first (s)
A = i = j + 1 to n
IF s(i] not = "-" THEN
IF s[i] >= f[j]|
THEN A = A U {i}
s[i] = "-"
j = i
return A

Answer 2

An activity-selection is the problem of scheduling a resource among several competing activity.

Statement: Given a set S of n activities with and start time, Si and fi, finish time of an ith activity. Find the maximum size set of mutually compatible activities.

Compatible Activities
Activities i and j are compatible if the half-open internal [si, fi) and [sj, fj) do not overlap, that is, i and j are compatible if si ≥ fj and sj ≥ fi
Greedy Algorithm for Selection Problem

I. Sort the input activities by increasing finishing time.
f1 ≤ f2 ≤ . . . ≤ fn

II Call GREEDY-ACTIVITY-SELECTOR (Sif)

n = length [s]
A={i}
j = 1
FOR i = 2 to n
do if si ≥ fj
then A= AU{i}
j = i
Return A

Operation of the algorithm
Let 11 activities are given S = {p, q, r, s, t, u, v, w, x, y, z} start and finished times for proposed activities are (1, 4), (3, 5), (0, 6), 5, 7), (3, 8), 5, 9), (6, 10), (8, 11), (8, 12), (2, 13) and (12, 14).

A = {p} Initialization at line 2
A = {p, s} line 6 - 1st iteration of FOR - loop
A = {p, s, w} line 6 -2nd iteration of FOR - loop
A = {p, s, w, z} line 6 - 3rd iteration of FOR-loop
Out of the FOR-loop and Return A = {p, s, w, z}

Analysis
Part I requires O(nlgn) time (use merge of heap sort).
Part II requires Theta(n) time assuming that activities were already sorted in part I by their finish time.

CORRECTNESS
Note that Greedy algorithm do not always produce optimal solutions but GREEDY-ACTIVITY-SELECTOR does.

Theorem: Algorithm GREED-ACTIVITY-SELECTOR produces solution of maximum size for the activity-selection problem.

Proof Idea: Show the activity problem satisfied
I. Greedy choice property.
II. Optimal substructure property

Proof:
I. Let S = {1, 2, . . . , n} be the set of activities. Since activities are in order by finish time. It implies that activity 1 has the earliest finish time.
Suppose, A is a subset of S is an optimal solution and let activities in A are ordered by finish time. Suppose, the first activity in A is k.
If k = 1, then A begins with greedy choice and we are done (or to be very precise, there is nothing to proof here).
If k not=1, we want to show that there is another solution B that begins with greedy choice, activity 1.
Let B = A - {k} U {1}. Because f1 =< fk, the activities in B are disjoint and since B has same number of activities as A, i.e., |A| = |B|, B is also optimal.

II. Once the greedy choice is made, the problem reduces to finding an optimal solution for the problem. If A is an optimal solution to the original problem S, then A` = A - {1} is an optimal solution to the activity-selection problem S` = {i in S: Si >= fi}.
why?

If we could find a solution B` to S` with more activities then A`, adding 1 to B` would yield a solution B to S with more activities than A, there by contradicting the optimality.

Dynamic-Programming Algorithm for the Activity-Selection Problem

Problem: Given a set of activities to among lecture halls. Schedule all the activities using minimal lecture halls.
In order to determine which activity should use which lecture hall, the algorithm uses the GREEDY-ACTIVITY-SELECTOR to calculate the activities in the first lecture hall. If there are some activities yet to be scheduled, a new lecture hall is selected and GREEDY-ACTIVITY-SELECTOR is called again. This continues until all activities have been scheduled.

LECTURE-HALL-ASSIGNMENT (s,f)

n = length [s)
FOR i = 1 to n
DO HALL [i] = NIL
k = 1
WHILE (Not empty (s))
Do HALL [k] = GREEDY-ACTIVITY-SELECTOR (s, t, n)
k = k + 1
RETURN HALL

Following changes can be made in the GREEDY-ACTIVITY-SELECTOR (s, f) (CLR).

j = first (s)
A = i
FOR i = j + 1 to n
DO IF s(i) not= "-"
THEN IF

GREED-ACTIVITY-SELECTOR (s,f,n)

j = first (s)
A = i = j + 1 to n
IF s(i] not = "-" THEN
IF s[i] >= f[j]|
THEN A = A U {i}
s[i] = "-"
j = i
return A

CORRECTNESS:
The algorithm can be shown to be correct and optimal. As a contradiction, assume the number of lecture halls are not optimal, that is, the algorithm allocates more hall than necessary. Therefore, there exists a set of activities B which have been wrongly allocated. An activity b belonging to B which has been allocated to hall H[i] should have optimally been allocated to H[k]. This implies that the activities for lecture hall H[k] have not been allocated optimally, as the GREED-ACTIVITY-SELECTOR produces the optimal set of activities for a particular lecture hall.

Analysis:
In the worst case, the number of lecture halls require is n. GREED-ACTIVITY-SELECTOR runs in θ(n). The running time of this algorithm is O(n2).

Observe that choosing the activity of least duration will not always produce an optimal solution. For example, we have a set of activities {(3, 5), (6, 8), (1, 4), (4, 7), (7, 10)}. Here, either (3, 5) or (6, 8) will be picked first, which will be picked first, which will prevent the optimal solution of {(1, 4), (4, 7), (7, 10)} from being found.
Also observe that choosing the activity with the least overlap will not always produce solution. For example, we have a set of activities {(0, 4), (4, 6), (6, 10), (0, 1), (1, 5), (5, 9), (9, 10), (0, 3), (0, 2), (7, 10), (8, 10)}. Here the one with the least overlap with other activities is (4, 6), so it will be picked first. But that would prevent the optimal solution of {(0, 1), (1, 5), (5, 9), (9, 10)} from being found.

example

1. using System;  
2. using System.Collections.Generic;  
3.   
4. namespace ActivitySelection  
5. {  
6.     class ActivitySelector  
7.     {  
8.         //Number of time slots  
9.         private int n = 11;  
10.   
11.         //Array of time slots  
12.         private int[,] A;  
13.   
14.         //Constructor  
15.         public ActivitySelector()  
16.         {  
17.             //Sample time slot array. Note that we are assuming  
18.             //the array is already sorted by finish time in an  
19.             //increasing order. It is a two dimensional array  
20.             //where A[i, 0] is the start time of time slot (i)  
21.             //and A[i, 1] is the finish time of time slot (i)  
22.             A = new int[11, 2]  
23.             {  
24.                 {10, 12},  
25.                 {10, 12},  
26.                 {10, 12},  
27.                 {11, 13},  
28.                 {12, 14},  
29.                 {13, 15},  
30.                 {14, 16},  
31.                 {16, 18},  
32.                 {16, 18},  
33.                 {16, 18},  
34.                 {17, 19}  
35.             };  
36.         }  
37.   
38.         public void Select()  
39.         {  
40.             //First time slot is by default part of the  
41.             //solution  
42.             Console.WriteLine(A[0, 0] + "-" + A[0, 1]);  
43.   
44.             //j index points to the time slot that was  
45.             //added to the optimum solution  
46.             int j = 0;  
47.   
48.             //Loop in the list of activities until  
49.             //reaching a time slot that does not  
50.             //overlap with slot (j)  
51.             for (int i = 1; i < n; i++)  
52.             {  
53.                 //If the (i) activity has a start time  
54.                 //greater than or equal to the finish  
55.                 //time of the (j) activity then add the  
56.                 //(i) activity to the solution  
57.                 if (A[i, 0] >= A[j, 1])  
58.                 {  
59.                     Console.WriteLine(A[i, 0] + "-" + A[i, 1]);  
60.   
61.                     //Update (j)  
62.                     j = i;  
63.                 }  
64.             }  
65.         }  
66.     }  
67.   
68.     //Main program  
69.     class Program  
70.     {  
71.         //Main  
72.         static void Main(string[] args)  
73.         {  
74.             //Create object  
75.             ActivitySelector selector = new ActivitySelector();  
76.             //Demo algorithm  
77.             selector.Select();  
78.         }  
79.     }  
80. }