시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 417 | 92 | 70 | 29.289% |
당신은 친구를 도와 새로운 카풀 앱을 개발해야 한다. 그 중 운전자와 승객을 매칭 시켜주는 알고리즘을 당신이 개발해야 한다. 현재 이 앱은 베타 버전이기 때문에 동-서로 길게 늘어진 고속도로 위에 위치한 지역에서만 서비스를 하고 있으며 아래와 같은 제한이 있다.
당신은 이 조건들을 만족하면서 최대한 많은 승객-운전자를 매칭시키는 알고리즘을 작성해야 한다.
예를 들어, 3명의 승객과 3명의 운전자가 있을 때, x, y, z 값이 아래와 같다고 하자.
이 경우 승객 1, 2, 3은 각각 정확 10미터, 20미터, 30미터 떨어진 곳으로 가고 싶어하며, 운전자 1은 정확히 8미터 떨어진 곳에 가려는 승객을 태울 의향이 있고, 운전자 2는 2미터 이상 18미터 이하 떨어진 곳에 가려는 승객을 태울 의향이 있고, 운전자 3은 25미터 이상 35미터 이하 떨어진 곳에 가려는 승객을 태울 의향이 있다.
이 경우, 승객1-운전자2, 승객3-운전자3을 매칭시켜주면 총 두 쌍을 매칭시킬 수 있고 이보다 많은 수의 승객-운전자를 매칭 시킬 수 있는 방법은 없다.
입력으로 N, M, 그리고 x, y, z 값들을 입력 받아 최대한 많은 승객-운전자 쌍을 매칭시키면 몇 쌍을 매칭 시킬 수 있는지 계산하는 프로그램을 작성하시오.
첫 줄에 테스트 케이스의 수 T가 주어진다 (1 ≤ T ≤ 10).
각 테스트 케이스의 첫 줄에는 N, M 이 주어진다.
그 다음 줄에 xi 가 공백으로 구분되어 주어진다 (1 ≤ xi ≤ 1,000,000,000).
다음 M줄에 걸쳐 각 줄에 yj 와 zj 가 공백으로 구분되어 주어진다 (1 ≤ yj ≤ zj ≤ 1,000,000,000).
각 테스트 케이스에 대해, 최대한 많은 승객-운전자를 매칭 시켰을 때 몇 쌍을 매칭시킬 수 있는지 출력한다.
3 3 3 10 20 30 8 8 2 18 25 35 4 4 2 3 4 5 1 4 2 4 3 5 3 4 3 3 1 2 3 10 20 30 40 50 60
2 4 0