from random import randint

class Interval:
    def __init__(self,d,f,v):
        self.debut=d
        self.fin=f
        self.valeur=v

    def Intersect(self, otherInt):
        return( (self.debut <= otherInt.fin) and (self.fin >= otherInt.debut))

    def __str__(self):
        return ("[{},{}] val={}".format(self.debut,self.fin,self.valeur) ) 

def GetEarliest(Dict_of_Interval, Active):
    earliest=+10**6
    for mykey  in Active:
        theInter= Dict_of_Interval[mykey] 
        if theInter.debut < earliest:
            earliest= theInter.debut
            bestid= mykey
    return bestid

def GreedyEarliest(L):
    Active=list(L.keys())
    # Active est l'ensemble des Intervales actif,
    # plus exactement Active contient les clefs/id des intervales actifs 
    # Au debut tout les intervales sont actif
    
    Solution= []
    # La solution courante est vide

    while len(Active) >0 : 
    ## Tnat qu'il reste des intervals actifs

        MonChoixGlouton = GetEarliest(L,Active)

        print("k", MonChoixGlouton,  L[MonChoixGlouton])
        # MonChoixGlouton contient la clef de l intervale choisi
        #On ajoute l'intervale à la solution

        Interval_choisi= L[MonChoixGlouton]
        Solution += [MonChoixGlouton]

        print ("interval numero {} =  {} est choisi ".format(MonChoixGlouton ,Interval_choisi))
    
        ## Il faut maintenant supprimer les intervales actifs qui intersecte l'intervale choisit
        Next=[]
        for index in Active :
            if not ( Interval_choisi.Intersect( L[index])):
                ## ici L[index] n est pas en conflit avec Interval_choisi
                Next+=[index]
        Active=list(Next)


        
    
def RandomInstance(nint, largeur):
    #Cree une instance aleatoire, soit un
    #dictionnaire de  nint intervales  qui sont dans  0,largeur
    Res={}
    for interkey in range(nint):
        deb =randint(0,largeur)
        fin =randint(0,largeur)
        if (fin < deb):
            (deb,fin)=(fin,deb)
        Res[interkey]= Interval(deb,fin, randint(0,5))
    return(Res)




def FindLoad(L):
    # determine la charge de chaque extremite d'un ensemble d'intervale
    debut={}
    fin={}
    Load={}
    #debut[ex] et fin[ex] vont contenir le nombre d' intervales qui
    #s arretent (debutent) en l extremite de nom ex
    #le nom de l extremite est tout simplement le nombre (a priori entier) ou elle est situee
    
    for index, inter in L.items():
        ## Pour tout les intervales on incremente de 1
        ##  la valeur de la clef de debut de son debut et idem pour la valeur de la clef de fin 
        debut[inter.debut]= debut.get(inter.debut,0)+1
        fin[inter.fin]= fin.get(inter.fin,0)+1

    #ceci est l ensemble des extremite
    extremites= set(debut.keys() ) | set(fin.keys())
    #on utilise un ensemble pour eviter d avoir une extremite deux fois
    
    # attention ici extremites est normalement trie
    # si tel n etait pas le cas on peut ajouter
    # extremite= list(extremite)
    # extremite.sort()
    currentload=0
    pred=-1
    # pred est le nom de l extremite precedente

    for ex in extremites:
        currentload+= debut.get(ex,0) - fin.get(pred,0)
        # on augmente la charge par le nombre d' intervales qui debutent en ex
        # on diminue par nombre d' intervales qui s arretaient `a l extremite precedente/
        Load[ex]=currentload
        print (" extremite {} , start {}, stop {} load {}" .format(ex, debut.get(ex,0),fin.get(pred,0) ,currentload))
        pred=ex



    #ici une facon peu efficace de determiner la charge des intervales :
    # on peut proceder comme pour les extremite
    Iload={}

    for interID, inter  in L.items():
        interExtremites=[ ex for ex in extremites if ex >= inter.debut and ex <=inter.fin]
        Iload[interID] = max ([ Load[x] for x in interExtremites])

    
    for interID,inter in L.items():
        print (inter, "load", Iload[interID]) 
    return (Iload)