문제

https://www.acmicpc.net/problem/1946

---

입력

첫째 줄에는 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스의 첫째 줄에 지원자의 숫자 N이 주어진다.
둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다.

---

출력

각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

---

풀이

제한조건

• T(1 ≤ T ≤ 20)
• N(1 ≤ N ≤ 100,000)
• 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

접근방법

그리디 + 정렬

입력으로 주어지는 값들이 모두 선발된 상태가 아니라는 점에 주의하자.
적절히 선발하여 가장 많이 뽑을 수 있도록 하는 문제이다.

예제 입력을 기준으로 살펴보자.

2
5
3 2 <- 선발
1 4 <- 선발
4 1 <- 선발
2 3 <- 선발
5 5
7
3 6
7 3
4 2 <- 선발
1 4 <- 선발
5 7
2 5
6 1 <- 선발

선발된 인원을 어떻게 찾을 수 있을지 생각해보자.
선발할 수 있는 조건은 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자이다.

즉 지원자의 점수가 (A,B)꼴 일때, A는 오름차순, B는 내림차순으로 정렬을 해보자.

// Case 1
1 4
2 3
3 2
4 1
5 5


// Case 2
1 4
2 5
3 6
4 2
5 7
6 1
7 3

A의 값은 같거나 점점 증가하고,
B의 값은 같거나 점점 감소한다.
따라서 아래로 순회하며, B의 값이 최저값을 갱신하는 순간마다 모두 선발해 준다면,
자연스럽게 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자를 선발할 수 있다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = stoi(in.readLine());

		StringBuilder sb = new StringBuilder();
		for (int tc = 0; tc < T; ++tc) {
			int N = stoi(in.readLine());
			List<int[]> list = new ArrayList<>();
			for (int i = 0; i < N; ++i) {
				String[] inputs = in.readLine().split(" ");
				list.add(new int[] {stoi(inputs[0]), stoi(inputs[1])});
			}
			Collections.sort(list, (a, b) -> {
				if (a[0] == b[0])
					return b[1] - a[1];
				return a[0] - b[0];
			});

			int second = list.get(0)[1];
			int answer = 1;
			for (int i = 1; i < N; ++i) {
				if (second > list.get(i)[1]) {
					answer++;
					second = list.get(i)[1];
				}
			}
			sb.append(answer).append("\n");
		}
		System.out.println(sb);
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}