[プログラマー/greedy/level 3]管制カメラ

9391 ワード
greedy せいぎょカメラ programmers level3 テキストリンク

1.コアタイプ


  • ギリシャ問題

  • ソートによる描画ロジックの適用

    • 2.問題解決策


  • 各車両が高速道路を出た地点(routes[1])に準じて昇順に並ぶ.
    (CollectionFrameworkが提供するソートはQuickSortを使用します.)


  • 車両を点検し、直前に車両が高速道路を離れた時点と次の車両の高速道路に進入した時点が重なっているかを確認する.
  • がオーバーラップしない場合、カメラを配置し、カメラを配置する候補位置(カメラ位置)を更新する.

    • 3.解題後の感想


    昨日解いた島の接続問題からいくつかのアイデアを得て、問題を解決しました.開始点と終了点がある場合は、ソートし、条件に従って問題を解決します.
    優先キューは問題を解決することもできますが、優先キューを使用する場合、追加した要素が特定の基準に従って並べ替えられた場合、優先キューが使用されるため、信頼キューが使用されて問題を解決します.
    (優先キューで問題を解くと、要素を追加するたびにソートされるため、タイムアウトが発生する可能性があります.)

    4.解題コード

    import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

class Solution {
    public int solution(int[][] routes) {
        List<Car> carList = new ArrayList<>();
        for (int i = 0; i < routes.length; i++) {
            carList.add(new Car(i, routes[i][0], routes[i][1]));
        }

        carList.sort(Comparator.comparingInt(Car::getEndPoint));

        int answer = 0;
        int cameraLocation = Integer.MIN_VALUE;
        for (Car car : carList) {
            if (cameraLocation >= car.getStartPoint()) {
                continue;
            }
            
            cameraLocation = car.getEndPoint();
            answer++;
        }

        return answer;
    }
}

class Car {
    private int index;
    private int startPoint;
    private int endPoint;

    public Car(int index, int startPoint, int endPoint) {
        this.index = index;
        this.startPoint = startPoint;
        this.endPoint = endPoint;
    }

    public int getIndex() {
        return index;
    }

    public int getStartPoint() {
        return startPoint;
    }

    public int getEndPoint() {
        return endPoint;
    }
}
    Markdown cheatsheet
    rogramers:変換単語-C++