カメラ

カメラ
まず区間を昇順に並べ,まだ重複していない区間については,前からできるだけ多く重ね,答えを1に増やした.
このとき、重なるたびに左と右が変わり、更新が必要になります.
コードは次のとおりです.

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

using namespace std;

int solution(vector<vector<int>> routes) {
    int answer = 0;
    
    sort(routes.begin(), routes.end());
    vector<int> visited(routes.size(), 0);
    for(int i=0;i<routes.size();i++) {
        if(visited[i])
            continue;
        answer++;
        int l = routes[i][0];
        int r = routes[i][1];
        for(int j=0;j<routes.size();j++) {
            if(visited[j])
                continue;
            if(routes[j][1] < l || routes[j][0] > r)
                continue;
            l = max(l, routes[j][0]);
            r = min(r, routes[j][1]);
            visited[j] = 1;
        }
    }
    
    return answer;
}