단속카메라

https://programmers.co.kr/learn/courses/30/lessons/42884
주어진 데이터는 차들이 이동한 위치(시작, 끝)이 들어오고 (시작, 끝)의 리스트가 여러개가 있을 때, 모든 지점을 포함할 수 있는 포인트의 최소 갯수를 구해야 합니다.
즉 교집합을 최대한 많이 포함하도록 포인트를 정하면 됩니다.
먼저 (시작, 끝) 으로 정의된 좌표를 시작 기준으로 오름차순 정렬합니다.
그러면 다음과 같이 접근할 수 있습니다.
먼저 (s1, e1)의 케이스와 (s2, e2)의 케이스를 비교할 수 있습니다.
오름차순으로 정렬하였으므로 s1 <= s2를 항상 만족합니다.
두번째로 s2와 e1간의 관계를 비교할 수 있습니다.
- 만약 s2 > e1이라면 (s1, e1)과 (s2, e2)는 교차되는 구간이 없습니다. 즉 교집합이 없으므로 (s1, e1) 구간에 포인트가 찍혀야 합니다.
  - 즉, s1…e1 // s2…e2 와 같이 구간이 전혀 겹치지 않습니다.
- 만약 s2 <= e1 이라면 겹치는 구간이 발생합니다.
  - 만약 e1 < e2 이면 s1…s2…e1…e2 의 순서가 됩니다. 이 때 (s1, e1), (s2, e2) 각각을 고려할 필요 없이 교집합인 (s2, e1)의 새로운 구간만 확인하면 됩니다.
    - 즉, (s1, e1), (s2, e2)는 버리고 (s2, e1)을 추가해서 고려합니다.
  - 만약 e1 >= e2 이면 s1…s2…e2…e1으로 (s2, e2)가 (s1, e1)에 완전히 포함됩니다. 이 때에도 교집합만 고려하면 되므로 (s1, e1)은 버립니다.

#include <vector>
#include <map>
#include <string>
#include <cstring>
#include <algorithm>>
#include <deque>
#include <iostream>
#include <queue>
#include <cmath>

using namespace std;

typedef pair<int, int> pi;
#define starts first
#define ends second

int solution(vector<vector<int>> routes) {
	int answer = 0;

	deque<pi> dq;
	for (int i = 0; i < routes.size(); ++i) {
		dq.push_back(pi(routes[i][0], routes[i][1]));
	}

	sort(dq.begin(), dq.end());

	while (!dq.empty()) {
		pi here = dq.front();
		dq.pop_front();
		int s1 = here.starts;
		int e1 = here.ends;

		if (dq.empty()) {
			answer++;
			break;
		}

		pi next = dq.front();
		int s2 = next.starts;
		int e2 = next.ends;

		if (s2 > e1) {
			answer++;
		}
		else if (s2 <= e1) {
			if (e1 < e2) {
				dq.pop_front();
				dq.push_front(pi(s2, e1));
			}
			else if (e1 >= e2) {
				;
			}
		}
	}

	return answer;
}