1    #-------------------------------------------------------------------------
2    # Eseménykiválasztási probléma
3    # MOHÓ ALGORITMUS
4    #
5    # Feladat:
6    # Valamely események egy közös eroforrást, például egy termet kívánnak
7    # használni. A teremben egy időben csak egy esemény folyhat.
8    # Egy esemény a kezdő és befejező indőpontja által adott (foglalas.txt).
9    # A cél a lehető legtöbb olyan eseménynek a kiválasztása,
10   # melyek nem ütik egymást!
11   #
12   #-------------------------------------------------------------------------
13   
14   fv=open('foglalas.txt','r')
15   h=[]        #ebben a listában tároljuk a kezdő és befejező időpontokat (k,b)
16   for sor in fv:
17       sor=sor.strip().split()         #a fájl egy sora --> lista
18       (k,b)=(int(sor[0]),int(sor[1])) #számpárok létrehozása
19       h.append((k,b))                 #h listába helyezése
20   fv.close()
21   
22   print('Rendezetlen eseménysorozat:\n', h)
23   
24   def befejezés_szerint(elem):
25       return elem[1]  #számpárban a második elemet jelenti
26   
27   #be kell rendezni a h listát a befejezési idők szerint
28   h=sorted(h,key=befejezés_szerint)
29   print('Rendezett eseménysorozat:\n', h)
30   
31   N=len(h)            #események száma
32   INTERVALLUMOK=[]
33   INDEX=[]
34   INDEX.append(0)     #mohó stratégia: az első esemény mehet a kiválasztások közé
35   INTERVALLUMOK.append(h[0])
36   i=0
37   for m in range(1,N):        #többi esemény ciklikus kiválasztása
38       if h[m][0]>=h[i][1]:    #ha adott esemény kezdőpontja >=már kiválasztott
39           INDEX.append(m)     #befejezési időpontjánál
40           INTERVALLUMOK.append(h[m])
41           i=m                 #m a kiválasztott esemény indexe,
42                                  #i=m miatt a következő cikluslépésben már ennek az
43                                  #eseménynek a végét nézzük
44   
45   print('Kiválasztott események indexei:\n', INDEX)
46   print('Kiválasztott események intervallumai:\n', INTERVALLUMOK)