#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Jan 15 08:15:26 2026

@author: adomps
"""



# ouvrir une figure avant d'exécuter cette fonction
def represente_une_tache(t, y, legende) :
    ''' Trace un segment horizontal à l'ordonnée y pour représenter
    la tache. '''
    #plt.plot(t, [y, y], linewidth = 4)
    plt.hlines(y, t[0], t[1], linewidth = 4)
    x_milieu = (t[0]+t[1])/2
    plt.text(x_milieu, y+0.1, legende)
    plt.yticks([], [])


t0 = [4, 7]
T =  [[47, 54], [16, 29], [36, 39],  [67, 80], [15, 17], [77, 82]]    
plt.figure()    
represente_une_tache(t0, 1, 't0')


## Représenter les tâches de T

###############################################################################
####         TACHES NON PONDÉRÉES               ###############################
###############################################################################

# Une tâche est une liste [t_debut, t_fin].
# On manipule des listes de tâches. Elles sont été triées par fins croissantes.

T1 = [[1, 4], [3, 4], [2, 5], [5, 8], [7, 9], [20, 23]]

T2 = [[-3, -1], [0, 2], [4, 5], [8, 9], [11, 13]]

T_Cormen = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 9], [5, 9], 
            [6, 10], [8, 11], [8, 12], [2, 14], [12, 16]]



def max_compatibles_rec(T, k) :
    ''' Renvoie récursivement une liste maximale de tâches compatibles choisies
    dans la liste T, supposée triée par fins croissantes. L'entier k désigne
    l'indice de la dernière tâche de T déjà sélectionnée. On recherche parmi 
    celles qui lui succèdent la première compatible. Pour le premier appel,
    prendre k = -1. '''
    n = len(T)  
    m = 

    if m < n : 
        return ...
    else :
        return ...
    




###############################################################################
###########  TÂCHES PONDÉRÉES                   ###############################
###############################################################################

 
Tex1 = [[0, 5, 0.34], [2, 6, 0.54], [4, 9, 1.2], [1.2, 12, 0.3], [8, 14, 0.8],
        [7, 15, 0.2], [12, 16, 0.4]]

# Exemple avec des tâches toutes compatibles.
Tex2 = [[0, 1, 0.3], [2, 3, 0.34], [4, 5, 0.43], [6, 7, 0.29], [8, 9, 0.21]]

# Exemple avec des tâches de poids unitaires. Cela équivaut à des
# tâches non pondérées.
T_Cormen = [[1, 4, 1], [3, 5, 1], [0, 6, 1], [5, 7, 1], [3, 9, 1], [5, 9, 1], 
            [6, 10, 1], [8, 11, 1], [8, 12, 1], [2, 14, 1], [12, 16, 1]]

# Tâches utilisés pour illuster la notion de dernier compatible
Tex3 = [[5, 20, 0.3], [1, 26, 0.4], [29, 54, 0.2], [42, 61, 0.4], [39, 66, 0.3],
        [65, 73, 0.2], [51, 79, 0.5], [58, 86, 0.4]]




def tabule_DC(T) :
    ''' Renvoie une liste contenant der_comp(i) pour tout i dans
    [0, n-1]. On évite d'utiliser itérativement la fonction der_comp,
    ce qui conduirait à une complexité quadratique. '''
    n = len(T)
    Numeros = [i for i in range(n)]  # liste des indices des tâches 
    Numeros.sort(key = lambda i : T[i][0]) # ordonnée selon leur début.
    
    DC = ['*' for i in range(n)] # valeurs bidons
    ind_conflit = 0

    for i in Numeros :     
        debut = ....
        while .... : 
            ind_conflit += 1
        
        DC[i] = ...
        
    return DC