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[] ]
C#
// The following implementation assumes
// that the activities are already sorted
// according to their finish time
using System;
class GFG {
// 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
public static void printMaxActivities(int[] s,
int[] f, int n)
{
int i, j;
Console.Write("Following activities are selected : ");
// The first activity always gets selected
i = 0;
Console.Write(i + " ");
// Consider rest of the activities
for (j = 1; j < n; j++) {
// 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]) {
Console.Write(j + " ");
i = j;
}
}
}
// Driver Code
public static void Main()
{
int[] s = { 1, 3, 0, 5, 8, 5 };
int[] f = { 2, 4, 6, 7, 9, 9 };
int n = s.Length;
printMaxActivities(s, f, n);
}
}
// This code is contributed
// by ChitraNayal
Producción:
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