백준 23740 버스 노선 개편하기

https://www.acmicpc.net/problem/23740

• 풀이
  주어진 N개의 노선들을 시작 구간을 기준으로 정렬 후, 스위핑 기법을 사용
  가장 오른쪽 버스 노선의 e가 s보다 작다면 새로운 버스 노선을 만들어야 하고 크다면 e와 min_val(요금)을 변경

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
#define ll long long
#define vc vector
#define vi vector<int>
#define vs vector<string>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

// 23740 버스 노선 개편하기

int N, cnt = 1;
vc<pair<pii, int>> v, ans;

int main(void) {
	fast;
	cin >> N;
	v.resize(N);
	for (int i = 0; i < N; ++i) cin >> v[i].first.first >> v[i].first.second >> v[i].second;
	sort(v.begin(), v.end());
	
	int s = v[0].first.first, e = v[0].first.second, mv = v[0].second;
	for (int i = 1; i < N; ++i) {
		if (v[i].first.first > e) {
			cnt++;
			ans.pb({ {s,e},mv });
			s = v[i].first.first, e = v[i].first.second, mv = v[i].second;
		}
		else {
			e = max(e, v[i].first.second);
			mv = min(mv, v[i].second);
		}
	}
	ans.pb({ {s,e},mv });
	cout << cnt << "\n";
	for (auto i : ans) cout << i.first.first << ' ' << i.first.second << ' ' << i.second << "\n";
}

• 스위핑 기법을 통해 쉽게 풀 수 있는 문제