プログラマーグリディカメラ

質問する

https://programmers.co.kr/learn/courses/30/lessons/42884

に答える

最後にプールを表示したディスクコントローラと同様にアクセスします.この問題をgreydiと理解してそれに近づくと、区間の大きな値(右の値)が最小であることを見つけて、すべての車両が完成するまで取り締まりカメラを繰り返し取り付けたことを容易に思い出すことができる.以下に示すように、粗末な絵で表現します.△この絵はちょっと変わっていて、その一節の大きさの関係を表しているように見えます.

この問題は、すべての車両が見えるように規制カメラの最小個数を設定するため、右の値が最小の終点を見つけ、規制カメラで発見された車両を消去すれば、監視カメラの最小個数を得ることができる.グリディが言った今の最善の選択が最良だと考えると、あなたは簡単に理解することができます.
ただ実装中に少しミスをしただけなのでタイムアウトしてしまい、最初は終了したのが削除だとタイムアウトになると思っていたので、ソート終了時に最大値を入れて後ろに置いて、一番前なら終了したコードを削除して、これでタイムアウトになりました.ほぼ整列の問題なので、O(n)が出るかと思いましたが、そうではないようです.したがって,後で1回のみ並べ替え,後で並べ替えずに最大値(done)のみを加えて完了すると,コードは無視される.

ミス

STLの使用は未熟で、インターネット

を参照する必要がある.

時間の複雑さは考慮されず、初期エラー(タイムアウト)

正しい答えを得るには逆さまに並ぶ必要がある場合が発生し、

このスタイルに時間がかかったと思います.

コード#コード#

エラーの最初のコード

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

using namespace std;

#define done 999999

bool compare(vector<int> front, vector<int> back){ // 비교함수 작성
    
    return front[1] < back[1];
    
    
}

int solution(vector<vector<int>> routes) {
    int answer = 0;
    
    sort(routes.begin(), routes.end(), compare);
    
    for(; routes[0][1] != done;){
        
        int emplace = routes[0][1];
        
        for(int i = 0; i < routes.size(); i++){
            
            if(routes[i][0] <= emplace && emplace <= routes[i][1]){
                
                routes[i][0] = done;
                routes[i][1] = done;
                
            }
            
        }
        
        sort(routes.begin(), routes.end(), compare);
        
        answer++;
        
        
    }
    
    return answer;
}

正しいコード

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

using namespace std;

#define done 999999

bool compare(vector<int> front, vector<int> back){ // 비교함수 작성
    
    return front[1] < back[1];
    
    
}

int solution(vector<vector<int>> routes) {
    int answer = 0;
    
    sort(routes.begin(), routes.end(), compare);
    
    for(;;){
        
        int emplace = done;
        
        for(int i = 0; i < routes.size(); i++){
            
            if(routes[i][1] != done){
                
                emplace = routes[i][1];
                break; // 여기 빠뜨림
                
            }
            
        }
        
        if(emplace == done)
            break;
        
        for(int i = 0; i < routes.size(); i++){
            
            if(routes[i][0] <= emplace && emplace <= routes[i][1]){
                
                routes[i][0] = done;
                routes[i][1] = done;
                
            }
            
        }
       
        answer++;
        
        
    }
    
    return answer;
}

改善

研究の結果、他の人は区間関係を通じて重複を減らし、最後に互いに交差していない含む関係だけを残し、計算を最小限に抑える方法を使ったが、私はそうしなかったので、時間的な損失が大きかった.(ログ(n^2)レベル)
しかし、私のように他の人のコードを突き刺して区間の最後に並べ替えて、監視カメラの最後の位置を覚えて、最後の監視カメラの領域に含めると、その区間の最後に新しい監視カメラを装着すれば、O(n)の時間内に問題を解決することができます.次回は簡単に考えたほうがいいですが、時間の複雑さも考えて、考えてから答えます.