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
輸入範例一： 5 160 180 150 200 280 300 300 330 190 210 輸入範例二： 1 120 120
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)
文章標籤
全站熱搜
