【Python】区間の重複を判定する3つの方法（累積和・ソート・座標圧縮）

3
10:00 12:00
11:30 13:00
14:00 15:00

def to_minutes(time_str):
    """HH:MM形式の文字列を0:00からの経過分数（整数）に変換する"""
    h, m = map(int, time_str.split(':'))
    return h * 60 + m


def get_input() :
    n = int(input())
    d = []
    for i in range(n):
        hhmm = input().split()
        d.append((to_minutes(hhmm[0]), to_minutes(hhmm[1])))
    return d


datas = get_input()
print(datas)

def to_minutes(time_str):
    """HH:MM形式の文字列を0:00からの経過分数（整数）に変換する"""
    h, m = map(int, time_str.split(':'))
    return h * 60 + m


def get_input() :
    n = int(input())
    d = []
    for i in range(n):
        hhmm = input().split()
        d.append((to_minutes(hhmm[0]), to_minutes(hhmm[1])))
    return d


def solve():
    intervals = get_input()    
        
    # 1日分の分数は 24 * 60 = 1440分
    # 余裕を持って少し大きめに確保（終了時刻の境界考慮）
    timeline = [0] * (24 * 60 + 2)

    # 開始時刻に+1, 終了時刻に-1を代入
    for start, end in intervals:
        timeline[start] += 1
        timeline[end] -= 1


    # 累積和
    for i in range(1, len(timeline)) :
        timeline[i] += timeline[i-1]

    # 重複チェック
    is_overlap = False
    
    for val in timeline:
        if val > 1:
            return True

    return False               


if __name__ == "__main__":
    is_overlap = solve()
    if is_overlap:
        print("重複あり")
    else:
        print("重複なし")

def to_minutes(time_str):
    """HH:MM形式の文字列を0:00からの経過分数（整数）に変換する"""
    h, m = map(int, time_str.split(':'))
    return h * 60 + m


def get_input() :
    n = int(input())
    d = []
    for i in range(n):
        hhmm = input().split()
        d.append((to_minutes(hhmm[0]), to_minutes(hhmm[1])))
    return d


def solve():
    intervals = get_input()    
        
    # 開始時刻でソートする
    # Pythonのsortはタプルの0番目の要素（開始時刻）で比較してくれる
    sorted_intervals = sorted(intervals)
    
    # 比較用：前のスケジュールの終了時刻
    # 最初は比較対象がないため、非常に小さい値にしておく
    last_end_time = -1
    
    for start, end in sorted_intervals:
        # 現在の開始時刻が、前の終了時刻より前なら重複
        if start < last_end_time:
            return True
        
        # 終了時刻を更新する
        #  包含関係（完全に内包されるケース）を考慮し、より遅い終了時刻を採用する。
        #  本問題では last_end_time = end で十分だが、一般化のため max を用いている
        last_end_time = max(last_end_time, end)          

    return False

if __name__ == "__main__":
    is_overlap = solve()
    if is_overlap:
        print("重複あり")
    else:
        print("重複なし")

def to_minutes(time_str):
    """HH:MM形式の文字列を0:00からの経過分数（整数）に変換する"""
    h, m = map(int, time_str.split(':'))
    return h * 60 + m


def get_input() :
    n = int(input())
    d = []
    for i in range(n):
        hhmm = input().split()
        d.append((to_minutes(hhmm[0]), to_minutes(hhmm[1])))
    return d


def solve():
    intervals = get_input()    
        
    # 座標圧縮のために、登場する全ての時刻を保持するセット
    points = set()
    
    for s, e in intervals:
        points.add(s)
        points.add(e)
    
    # 1. 座標圧縮: 登場する時刻をソートしてリスト化
    sorted_points = sorted(list(points))
    
    # 2. 各時刻がリストの何番目かを引ける辞書を作成
    # 例: {600: 0, 690: 1, 720: 2, ...}
    idx = {val: i for i, val in enumerate(sorted_points)}
    

    # 3. 圧縮後のサイズで配列を用意
    timeline = [0] * len(sorted_points)
    
    for start, end in intervals:
        s, e = idx[start], idx[end]
        
        # いもす法: 開始ランクに+1, 終了ランクに-1
        timeline[s] += 1
        timeline[e] -= 1
        

    # 4. 累積和
    for i in range(1, len(timeline)) :
        timeline[i] += timeline[i-1]

    # 5. チェック
    for val in timeline:
        if val > 1:
            return True
            
    return False

if __name__ == "__main__":
    is_overlap = solve()
    if is_overlap:
        print("重複あり")
    else:
        print("重複なし")

    # 座標圧縮のために、登場する全ての時刻を保持するセット
    points = set()
    
    for s, e in intervals:
        points.add(s)
        points.add(e)
    
    # 1. 座標圧縮: 登場する時刻をソートしてリスト化
    sorted_points = sorted(list(points))
    
    # 2. 各時刻がリストの何番目かを引ける辞書を作成
    # 例: {600: 0, 690: 1, 720: 2, ...}
    idx = {val: i for i, val in enumerate(sorted_points)}