Se le dan n actividades con sus horas de inicio y finalización. Seleccione el número máximo de actividades que puede realizar una sola persona, suponiendo que una persona solo puede trabajar en una sola actividad a la vez. Ejemplo:
Example 1 : Consider the following 3 activities sorted
by finish time.
start[] = {10, 12, 20};
finish[] = {20, 25, 30};
A person can perform at most two activities. The
maximum set of activities that can be executed
is {0, 2} [ These are indexes in start[] and
finish[] ]
Example 2 : Consider the following 6 activities
sorted by finish time.
start[] = {1, 3, 0, 5, 8, 5};
finish[] = {2, 4, 6, 7, 9, 9};
A person can perform at most four activities. The
maximum set of activities that can be executed
is {0, 1, 3, 4} [ These are indexes in start[] and
finish[] ]
Python
"""The following implementation assumes that the activities are already sorted according to their finish time""" """Prints a maximum set of activities that can be done by a single person, one at a time""" # n --> Total number of activities # s[]--> An array that contains start time of all activities # f[] --> An array that contains finish time of all activities def printMaxActivities(s, f ): n = len(f) print "The following activities are selected" # The first activity is always selected i = 0 print i, # Consider rest of the activities for j in xrange(n): # If this activity has start time greater than # or equal to the finish time of previously # selected activity, then select it if s[j] >= f[i]: print j, i = j # Driver program to test above function s = [1, 3, 0, 5, 8, 5] f = [2, 4, 6, 7, 9, 9] printMaxActivities(s, f) # This code is contributed by Nikhil Kumar Singh
Producción:
The following activities are selected 0 1 3 4
Consulte el artículo completo sobre el problema de selección de actividades | Codicioso Algo-1 para más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA