Planning alg

gistfile1.py

films = [
    (1998, 2008), # The presidents  
    (1999, 2005), # Descrite math
    (2001, 2009), # Tarjan
    (2005, 2009), # Halting
    (2007, 2011), # Steiner
    (2010, 2020), # the four volume
    (2012, 2018), # programming chall
    (2014, 2022), # process term
    (2018, 2020), # calculated bets
]


def get_longest(films):
    # print("enter")
    if len(films) == 1:
        return films

    res = []
    for begin, ends in films:
        possible = [i for i in films if i[0] >= ends]
        if possible:
            current = [(begin, ends)]
            current.extend(get_longest(possible))  # O(n!)
            res.append(current)
    # print("Res: %s" % res)
    return max(res, key=lambda x: len(x))  # (n*log(n)) ^^ move check to if


def get_long_opt(films):
    # |---|
    #  |------|  << opt
    #     |-----|
    # |---------|
    fin_first = min(films, key=lambda x: x[1])  # O(n) - unsorted array
    res = [fin_first]
    for s, e in films:  # O(n)
        print(".", end='')
        if (s, e) == fin_first:
            continue
        if s < fin_first[0] and e < fin_first[1]:
            print("REMOVE 1")
            films.remove((s,e))
        if s < fin_first[1]:
            print("REMOVE 2 %s < %s" % (s, fin_first[1]))
            films.remove((s,e))
        if s < fin_first[0] and e > fin_first[1]:
            print("REMOVE 3")
            films.remove((s,e))
    if len(films) > 1:
        res.extend(get_long_opt(films[1:])) # (O(n))
        return res
    return res


print(get_longest(films))
print(get_long_opt(films.copy()))  # O(n^2)