b966: 第 3 題 線段覆蓋長度 解題心得

題目來源：https://zerojudge.tw/ShowProblem?problemid=b966

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

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

這題跟某題方形覆蓋有點像，只是這題要算的是覆蓋長度，首先我們先將所有的線段根據起點由小到大排序，如此前後兩線段就只剩下三種可能。

EX：

1.(3 , 9)、(4 , 7)

2.(3 , 9)、(12 ,18)

3.(3 , 9)、(6 , 12)

只要處理好這三種情況，這題就可以迎刃而解。

以下附上程式碼，有什麼問題可以在下面留言或MAIL給我來討論囉。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	vector<pair<int, int>> vp;
	int n , m , o , q = 0 , len = 0;
	cin >> n;
	pair<int, int> p;
	while (q++ < n) {
		cin >> m >> o;
		p.first = m;
		p.second = o;
		vp.push_back(p);
	}
	sort(vp.begin(), vp.end());
	len = vp[0].second - vp[0].first;
	pair<int, int> sample = vp[0];
	for (int i = 1; i < n; i++) {
		if (vp[i].second <= sample.second) {
			continue;
		}
		else if (vp[i].first >= sample.second) {
			sample = vp[i];
			len += vp[i].second - vp[i].first;
		}
		else {
			len += vp[i].second - sample.second;
			sample.second = vp[i].second;
		}
	}
	cout << len;
}