高中生程式解題系統 b966: 第 3 題線段覆蓋長度－資工趴趴熊的小天地

Content

給定一維座標上一些線段，求這些線段所覆蓋的長度，注意，重疊的部分只能算一次。

例如給定 4 個線段：(5, 6)、(1, 2)、(4, 8)、(7, 9)，如下圖，線段覆蓋長度為 6 。

Input

第一列是一個正整數 N ，表示此測資有 N 個線段。
接著的 N 列每一列是一個線段的開始端點座標整數值 L 和結束端點座標整數值 R ，開始端點座標值小於等於結束端點座標值，兩者之間以一個空格區隔。

其中 30%的測資滿足， N < 100 ， 0 ≤ L , R < 1000 ，並且線段沒有重疊。
其中 70%的測資滿足， N < 100 ， 0 ≤ L , R < 1000 ，並且線段可能重疊。
其中100%的測資滿足， N < 10000 ， 0 ≤ L , R < 10000000 ，並且線段可能重疊。

Output

輸出其總覆蓋的長度。

本題為嚴格比對，請務必按照說明進行輸出。

Sample Input #1

Sample Output #1

輸出範例一：
110

輸出範例二：
0

Python:

"""
解題思路:
要比的線段先把左值由小到大排列，確保等下比對時，線永遠不會有左移的狀況產生
排序完後進行比對:

1.新左值>舊右值:有一條完全的新線(一定要先寫!)
2.新右值>舊右值:線段增長
3.新右值<舊右值:沒事忽略(不寫)
"""
from sys import stdin
n=int(stdin.readline())
f=[]
for _ in range(n):
    f.append([int(x) for x in stdin.readline().split()])#將那一行輸入的樹變成list嘉進大list
f.sort(key=lambda x:x[0])
"""排序完成，接下來要抓數字"""
o1,o2=f.pop(0) #因為f[0]是兩個數字，要用兩個變數接
r=(o2-o1)
for n1,n2 in f:
    if n1>o2:#這個條件一定要先放在前面!!!，因為會有n1,n2都大於o1,o2狀況
        r+=(n2-n1)
        o1,o2=n1,n2
        
    if n2>o2:
        r+=(n2-o2)
        o2=n2
        
    
print(r)