# Bracket Sequences I — スタックを使った O(n) 解法
def is_valid_brackets(s: str) -> bool:
    stack = 0
    for c in s:
        if c == '(':
            stack += 1
        elif c == ')':
            if stack == 0:
                return False
            stack -= 1
    return stack == 0

print(is_valid_brackets('(())()'))  # True
print(is_valid_brackets('((())'))   # False

# Movie Festival — 貪欲法 O(n log n)
def movie_festival(movies):
    movies.sort(key=lambda x: x[1])  # 終了時刻でソート
    count, last_end = 0, 0
    for start, end in movies:
        if start >= last_end:
            count += 1
            last_end = end
    return count

print(movie_festival([(1,3),(2,5),(3,7),(4,6),(6,8)]))  # 3