APCS Mar 2016 - b966 Q3 [Python]

本題敘述：

給定一維座標上一些線段，求這些線段所覆蓋的長度，注意，重疊的部分只能算一次。 例如給定 4 個線段：(5, 6)、(1, 2)、(4, 8)、(7, 9)，如下圖，線段覆蓋長度為 6 。

def main():
    # 讀取線段數量
    n = int(input())

    segments = []

    # 讀取每個線段的起點和終點
    for _ in range(n):
        L, R = map(int, input().split())
        segments.append((L, R))

    # 將線段按照起點進行排序
    segments.sort(key=lambda x: x[0])

    # 合併線段
    covered_length = 0
    current_start, current_end = -1, -1

    for start, end in segments:
        if start > current_end:

            # 如果當前線段與前一線段不重疊，加上前一線段的長度(因為上一步不知道下一個是否比自己大)
            covered_length += current_end - current_start
            current_start, current_end = start, end
        else:
            # 如果重疊，延伸線段的結束點
            current_end = max(current_end, end)

    # 加上最後一個線段的長度
    covered_length += current_end - current_start

    # 輸出結果
    print(covered_length)


if __name__ == "__main__":
    main()
    

本題知識

• map 用法：map(func,obj)

  Ex:

  map(int,input(),split())
  

• sort 用法：[(這是陣列)].sort(key=func)

  Ex:

  the_list = [(0,6),(3,8),(5,7),(2,5),(1,10),(8,12),(7,10)]
  the_list.sort(key= lamba x:x[0])