Quel algorithme utiliser pour ce problème?

Question

J'ai récemment été confronté à un test d'entrevue Hackerrank où je ne pouvais pas résoudre correctement le problème suivant. Je ne voudrais pas nommer le problème exact à des fins de la vie privée, mais je peux dire que c'était nulle part dans Google avec ce nom.

problème

Nous voulons organiser un événement avec autant d'interprètes que possible. On nous donne une liste de temps d'arrivée d'interprète possibles et de durées de performance. Notre fonction doit renvoyer le nombre maximum d'interprètes pouvant être sélectionné sans conflit.

exemple

n= 5
Arrivées= [1, 3, 3, 5, 7] (interprètes arrivent dans ces temps)
Durations= [2, 2, 1, 2, 1] (le temps nécessaire pour finir leurs performances)
Solution= 4

Donc, au temps 1, nous pouvons accepter l'artiste et finira à l'heure 3. Au temps 3, nous avons deux choix conflictuels et peu importe que nous avons choisi. Le temps 5 et 7 ne sont pas conflictuels non plus.

ma solution

1. fait des tuples des arrivées et des durées en zipping. Tri des tuples d'abord à l'arrivée, puis sur la durée.
2. extérieur pour le cycle pour i du début à la fin. Initialiser un nouvel ensemble dans chaque iTER.
3. interne pour le cycle de j de i à finir. Vérifiez si J peut être ajouté à l'ensemble sans conflit. Si le jeu est plus long que max, je sauvegarde.

Source Python

questions

1. Y a-t-il de meilleures façons, des algorithmes standard pour résoudre ce problème?
2. Je sais qu'il y a des cas de bord, pour lesquels mon algorithme ne fonctionne pas. HackErkank a évalué mon algo, et il n'a passé que 7/13 cas de test. Qu'est-ce qui pourrait être des cas de bord que je manque?
3. Est-ce un problème de recherche ou un problème d'optimisation?

Answer 1

Ceci est un simple Programmation de planification d'intervalle de planification problème, qui peut être résolu dans < em> o (n journal (n)) temps via un simple algorithme gourmand. L'astuce consiste à trier les performances selon temps de fin et non heure de début .

.

Voici la description de la solution trouvée sur la page Wikipedia que j'ai liée:

---

Plusieurs algorithmes, qui peuvent sembler prometteurs à première vue, ne trouvent pas la solution optimale:

• Sélection des intervalles qui commencent plus tôt, ce n'est pas une solution optimale, car si le plus ancien intervalle est très long, l'accepterait de nous faire rejeter de nombreuses autres demandes plus courtes.

• Sélection des intervalles les plus courts ou de sélectionner des intervalles avec le moins de conflits n'est pas non optimal.

Solution polynomiale gourmande

L'algorithme gourmand suivant trouve la solution optimale:

Select the interval, x, with the earliest finishing time.
Remove x, and all intervals intersecting x, from the set of candidate intervals.
Repeat until the set of candidate intervals is empty.

Chaque fois que nous sélectionnons un intervalle à l'étape 1, nous devrons peut-être supprimer de nombreux intervalles à l'étape 2. Toutefois, tous ces intervalles franchissent nécessairement le temps de finition de X, et ils se croisent donc tous. Par conséquent, au plus 1 de ces intervalles peuvent être dans la solution optimale. Par conséquent, pour chaque intervalle dans la solution optimale, il y a un intervalle dans la solution gourmande. Cela prouve que l'algorithme gourmand trouve effectivement une solution optimale.

Une explication plus formelle est donnée par un Argument de charge .

L'algorithme gourmand peut être exécuté dans le temps o (n log n) , où n est le nombre de tâches, à l'aide d'une étape de prétraitement dans laquelle les tâches sont triées. par leurs temps de finition.

---

Answer 2

regarder Planification maximale d'intervalle .

Attribuer un intervalle $ (S_I, T_I) $ à chaque interprète, pour $ i= 1, \ points, N $ , ce qui signifie que la performance commence à l'heure $ s_i $ et a une durée de $ t_i - s_i $ .

suppose pour l'instant que tous les intervalles sont triés par leur temps de fin. Juste pour la simplicité suppose que toutes les heures sont distinctes (cette hypothèse est inutile). Votre problème peut alors être résolu dans $ o (n) $ temps.

considérer $ (s_1, t_1) $ et let $ i $ être l'ensemble des intervalles qui intersectez-le (à l'exclusion de $ (s_1, t_1) $ elle-même).

est facile de voir que tous les intervalles dans $ i $ doivent démarrer avant $ t_1 $ ( Comme autrement, ils ne seraient pas intersect $ (s_1, t_1) $ ) et se terminent après $ t_1 $ ( sinon $ t_1 $ ne serait pas l'heure de fin minimum). Cela signifie que tous les intervalles dans $ i \ tasse \ \ \ {(S_1, t_1) \ \} $ se croisent les uns avec les autres et, partant, une solution peut contenir au maximum l'un d'entre eux.

let $ S $ être une solution (c'est-à-dire un sous-ensemble d'intervalles de non-intersection par paires). Il est toujours possible de convertir $ s $ dans une nouvelle solution $ s '$ qui contient $ (s_1, t_1) $ et telle que $ | s '| \ ge | s | $ .

si $ s \ cap i=videtyset $ nous sommes trivialement terminés car nous pouvons choisir $ S '= S \ tasse \ {(s_1, t_1) \ \} $ (remarquez que cela inclut également le cas dans lequel $ (s_1, t_1) \ in s $ ).

si $ s \ cap i \ neq \ videtyt $ , laisse $ (s_i, t_i) $ Soyez l'intervalle unique dans $ S \ CAP I $ . Tout intervalle $ (s_j, t_j) \ in s \ seminus \ {(s_i, t_i) \} $ doit satisfaire soit $ S_J> T_I> T_1 $ ou $ s_i> t_j> t_1 $ . Ce dernier cas est en fait impossible puisqu'il contredit le fait que $ (S_I, T_I) \ en S $ . En d'autres termes, si nous remplaçons $ (s_i, t_i) $ avec $ (s_1, t_1) $ Nous obtenons toujours une solution réalisable. Par conséquent, nous choisissons $ s '= s \ tasse \ {((S_1, t_1) \} \ seminus \ {(S_I, T_I) \} $

.

.

.

La ligne de fin de la ligne est qu'il y a toujours une solution optimale contenant $ (S_1, T_1) $ . Par conséquent, vous pouvez toujours ajouter $ (s_1, t_1) $ à votre solution, supprimez tous les intervalles dans $ s \ tasse \ { (S_1, T_1) \} $ et recherchez la solution optimale entre les intervalles restants. Cela revient à exécuter l'algorithme gourmand qui considère les intervalles dans l'ordre et ajoute tout intervalle qui convient.

De votre instance, il semble que les temps de départ soient déjà triés. Dans ce cas, vous pouvez faire le tour de "inverser l'heure", c'est-à-dire d'échanger les heures de départ et de fin, par exemple en changeant $ (s_i, t_i) $ $ (- t_i, -s_i) $ , qui vous permet d'obtenir une $ o (n) $ Algorithme de temps en ignorant l'étape de tri initiale qui nécessiterait déjà $ \ oméga (n \ journal n) $

heure.