[BOJ] 1946. 新入社員

9907 ワード
greedy cpp python boj テキストリンク
1946.新入社員

1.質問


いつでも最高の大企業陣営の株式会社だけを求めて新入社員募集を実施する.人材選抜試験は第1回書類審査と第2回面接からなる.最高の企業理念だけを追求し、最も優秀な人材を従業員として選抜したいと考えています.
そのため、珍栄株式会社は、他のすべての応募者に比べて、書類審査成績と面接成績のうち少なくとも1人が他の応募者を下回らないという原則を制定した.つまり、ある応募者Aの成績が他の応募者Bの成績に比べて書類審査の結果も面接の成績も低下すれば、Aは絶対に選ばれないということです.
これらの条件を満たす場合は、珍栄株式会社が今回の新入社員募集で選抜できる新入社員の最大人数を要求する計画を立ててください.

2.入力


第1行は、試験例の個数T(1≦T≦20)を与える.各試験例の最初の行は、ボランティアの数N(1≦N≦100000)を与えた.2行目からN行目では、応募者ごとの書類審査成績、面接成績の順位が空白で1行になっています.どちらの成績順も1位からN位までは上下しないと仮定している.

3.出力


各テストケースについて、珍栄株式会社は新入社員の最大人数を1行1行印刷することができます.

4.解答


Python
T = int(input())

for _ in range(T):
    N = int(input())
    scores = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x : x[0])
    # 서류심사 성적을 높은 순으로 정렬
    
    stack = []
    for score in scores:
        if not stack or stack[-1][1] > score[1]:
            stack.append(score)
    # 1등은 무조건 포함되므로 1등을 기준으로 차례대로 면접 순위가 낮은 사람을 선발하기
    
    print(len(stack))
C++
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair<int, int> P;

int main() {
    int T;
    cin >> T;
    
    for (int i = 0; i < T; i++) {
        int N;
        cin >> N;
        
        vector<P> v;
        for (int j = 0; j < N; j++) {
            int x, y;
            cin >> x >> y;
            v.push_back(make_pair(x, y));
        }
        sort(v.begin(), v.end());
        
        vector<P> v1;
        for (auto p : v) {
            if (v1.size() == 0 || v1.back().second > p.second) {
                v1.push_back(p);
            }
        }
        
        cout << v1.size() << endl;
    }
}
zabbix4.0ローカルインストールの詳細と手順
IntersectionObserver APIによる遅延負荷