[알고리즘] c++ cpp 단속카메라

포인트

1. 그리디 문제이며 단속카메라는 회의실 배정 문제하고 유사하다고 볼 수 있습니다. 

2. 회의실 배정문제는 제일 많은 회의를 하기 위해 끝나는 시간을 기준으로 정렬을 하였습니다. 
하지만 단속 카메라 문제의 경우 시작하는 시간을 기준으로 정렬을 한 점을 유의해주세요

2020/11/04 - [Algorithm] - [알고리즘] c++ cpp 회의실 배정

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> routes) {
	int camera = 1;
	sort(routes.begin(), routes.end()); //차량들의 고속도로 진입 지점 기준으로 소트
	int pointer = routes[0][1]; //첫 카메라 설치 위치는 가장 빨리 고속도로를 진입한 차의 진출 지점
	
	for (int i = 1; i < routes.size(); i++) {
		if (routes[i][1] < pointer) //i번째 차량의 진출 지점이 cposition(최근 설치한 카메라 위치) 이전에 있을 경우, cposition 값을 i번째 차량의 진출 지점으로 갱신
			pointer = routes[i][1];

		if (routes[i][0] > pointer) { //i번째 차량이 최근 설치한 카메라를 만나지 않을 경우, 새로운 카메라 설치 후 cposition 값을 i번째 차량의 진출 지점으로 갱신
			pointer=routes[i][1];
			camera += 1;
		}
	}
	return camera;
}