We have a set of activities that require stand-alone access to a common resource, given the form A = {a1, a2, ..., an}, so if the resource is reserved for one activity, that activity cannot be assigned to another activity until it has finished. • The activity needs the ai resource in the [si, fi] time interval. Here si indicates the start time of the activity and fi indicates the end time of the activity. You can think of the time values given here as positive integers. • The goal is to find the largest possible number of non-contagious activities, ie the time periods where they need common resources do not overlap. Assuming that the activities are presented in ascending order with respect to their start times, design an algorithm based on dynamic programming for the activity selection problem. Your algorithm should find and return the maximum number of non-overlapping activities that can be selected from a set of activities given in the above conditions. Just as you write your algorithm in pseudocode, express its path in your own sentences. Find the time complexity of your algorithm. Algorithm dynamicActivitySelection (A[1..n], S[1..n], F[1..n]) // Input : Activities array A, start times array S, end times array F // // The sequence of start times of activities is given in ascending order S[1]
We have a set of activities that require stand-alone access to a common resource, given the form A = {a1, a2, ..., an}, so if the resource is reserved for one activity, that activity cannot be assigned to another activity until it has finished.
• The activity needs the
• The goal is to find the largest possible number of non-contagious activities, ie the time periods where they need common resources do not overlap.
Assuming that the activities are presented in ascending order with respect to their start times, design an
Algorithm dynamicActivitySelection (A[1..n], S[1..n], F[1..n])
// Input : Activities array A, start times array S, end times array F
// // The sequence of start times of activities is given in ascending order S[1]<S[2]<S[3]<.....<S[n].
// The same index in all sequences corresponds to the same activity as the value in the eye.
// Output : The maximum number of activities that can be selected with non-overlapping time intervals.
Step by step
Solved in 2 steps
