<style>
.markdown-body table{
display: unset;
}
</style>

# APCS實作題2016年3月第3題：線段覆蓋長度

> 第1版：2023年2月8日
> 第2版：2023年10月19日
> 作者：王一哲
> 題目來源：[105年3月5日實作題第3題](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2020/10/APCS-%E5%AF%A6%E4%BD%9C%E9%A1%8C-2016.03.05.pdf)
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=b966)

<br />

## 題目

### 問題描述

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

<img height="80%" width="80%" src="https://i.imgur.com/ehcyKZl.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<br />

### 輸入格式

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

### 輸出格式

輸出其總覆蓋的長度。
<br />

### 範例一：輸入

<center>

| 輸入 | 說明 |
| --- | --- |
| 5 | 此組測試案例有 5 個線段 |
| 160 180 | 開始端點座標值與結束端點座標 |
| 150 200 | 開始端點座標值與結束端點座標 |
| 280 300 | 開始端點座標值與結束端點座標 |
| 300 330 | 開始端點座標值與結束端點座標 |
| 190 210 | 開始端點座標值與結束端點座標 |

</center>

### 範例一：正確輸出

<center>

| 輸入 | 說明 |
| --- | --- |
| 110 | 測試案例的結果 |

</center>

<br />

### 範例二：輸入

<center>

| 輸入 | 說明 |
| --- | --- |
| 1 | 此組測試案例有 1 個線段 |
| 120 120 | 開始端點座標值與結束端點座標 |

</center>

### 範例二：正確輸出

<center>

| 輸入 | 說明 |
| --- | --- |
| 0 | 測試案例的結果 |

</center>

<br />

### 評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(time limit)均為 2 秒，依正確通過測資筆數給分。每一個端點座標是一個介於 0~M 之間的整數，每組測試案例線段個數上限為 N。其中：
- 第一子題組 30 分，M<1000，N<100，線段沒有重疊。
- 第二子題組 40 分，M<1000，N<100，線段可能重疊。
- 第三子題組 30 分，M<10000000，N<10000，線段可能重疊。

<br />

## Python 程式碼

### 方法1：將端點的聯集存入串列

N = int(input())  # 從標準輸入讀取端點資料筆數 N
data = []  # 從標準輸入讀取端點存入 data
for _ in range(N):
    data.append(list(map(int, input().split())))

# 以左側端點為由小到大排序
data.sort(key = lambda x : x[0])

# 找出端點的聯集存入 points
points = [data.pop(0)]
for tmp in data:
    if tmp[0] > points[-1][1]:
        points.append(tmp)
    elif tmp[1] > points[-1][1]:
        points[-1][1] = tmp[1]

# 計算覆蓋長度 length
length = 0
for point in points:
    length += point[1] - point[0]

print(length)

<br />

1. 如果將測料存成 data.txt 並與程式碼 test.py 放在同一個資料夾中，於文字界面可以使用以下指令執行程式，就可以不需要每次執行程式時還需要手動輸入測資。

    python3 test.py < data.txt

2. 第7行，為了依照 data 當中每一組端點的左側端點排序，使用 sort 時時需要加上參數 key = lambda x:x[0]。
3. 第10行，先將 data[0] 取出存入串列 points。
4. 第11 ~ 15行，找出各組端點資料的聯集。
1. 依序從 data 中讀取端點資料並暫存成 tmp，若 tmp 左側端點位於 points 當中最後一組資料的右側端點的右側，代表這兩組端點資料沒有重疊，將 tmp 加到 points 最後面。
2. 若 tmp 左側端點位於 points 當中最後一組資料右側端點的左側，且 tmp 右側端點位於 points 當中最後一組資料右側端點的右側，則將 points 當中最後一組資料右側端點改寫成 tmp 右側端點。
3. 以範列一輸入資料為例，各組端點資料為 [[160, 180], [150, 200], [280, 300], [300, 330], [190, 210]]，其聯集為 [[150, 210], [280, 330]]。
5. 計算 points 各組端點間的距離，再加到變數 length 中，最後輸出 length 即為答案。
6. 於 ZeroJudge 測試結果，第99筆測試花費時間最久為 0.1 s，使用記憶體最多為 5.2 MB，通過測試。

<br />

### 方法2：讀取新的資料點同時更新覆蓋長度

N = int(input())  # 從標準輸入讀取端點資料筆數 N
data = []  # 從標準輸入讀取端點存入 data
for _ in range(N):
    data.append(list(map(int, input().split())))

# 以左側端點為由小到大排序
data.sort(key = lambda x : x[0])

# 計算覆蓋長度 length
start = data[0][0]
end = data[0][1]
length = end - start;

for i in range(1, N):
    if data[i][0] > end:
        start = data[i][0]
        end = data[i][1]
        length += end - start
    elif data[i][1] > end:
        length += data[i][1] - end
        end = data[i][1]

print(length)

<br />

1. 這支程式的運作邏輯大致上與 Python 程式碼方法1相同，不同之處在於第10 ~ 21行，先産生兩個記錄起點、終點用的變數 start 及 end，再用 start、end、data 計算線段覆蓋長度，不另外産生一個記錄線段聯集的 list。
2. 第15 ~ 18行，如果 data\[i\] 的左端點大於 end，代表這組端點覆蓋的區域與之前的區域不重疊，更新 start 及 end，長度 length 要再加上 end - start。
3. 第19 ~ 21行，如果 data\[i\] 的右端點大於 end，代表這組端點覆蓋的區域與之前的區域重疊，先將長度 length 加上 data\[i\]\[1\] - end，再將 end 更新為 data\[i\]\[1\]。
4. 於 ZeroJudge 測試結果，花費時間為 0.1 s，使用記憶體最多為 5.2 MB，通過測試。

<br /><br />

## C++ 程式碼

#include <iostream>
#include <algorithm>

using namespace std;

// 儲存資料用的格式，每個 Node 中有兩個數值 
typedef struct _node {
    int a;
    int b;
} Node;

// 排序用的比較式，依據左側起點由小到大排序，若起點相同則依右側終點由小到大排序
bool cmp(Node p, Node q) {
    if (p.a == q.a) return (p.b > q.b);
    else return(p.a < q.a);
}

int main(int argc, char* argv[]) {
    int n;
    Node data[10000];

    cin >> n;     // 讀取資料筆數
    for(int i=0; i<n; i++) cin >> data[i].a >> data[i].b;     // 讀取所有資料 
    sort(data, data+n, cmp);   // 依據左側起點由小到大排序，若起點相同則依右側終點由小到大排序 
    //for(int i=0; i<n; i++) cout << data[i].a << "\t" << data[i].b << endl; // 除錯用，印出排序後的資料

    int start = data[0].a;
    int end = data[0].b;
    int length = end - start;
    
    for(int i=1; i<n; i++) {
        if(data[i].a > end) {
            start = data[i].a;
            end = data[i].b;
            length += end - start;
        } else if(data[i].b > end) {
            length += data[i].b - end;
            end = data[i].b;
        }
        //cout << length << endl; // 除錯用，印出每次計算的結果
    }
    cout << length << endl;
    return 0;
}

<br />

1. 這支程式的運作邏輯與 Python 程式碼方法2相同，只是改成用 C++ 的語法。
2. 於 ZeroJudge 測試結果，第93筆測試費時最久為 22 ms，使用記憶體最多為 404 KB，通過測試。

<br />

---

###### tags:`APCS`、`Python`