대표 선수

면접 대비

시간 제한2초메모리 제한256 MB

요약
N개 학급에서 각각 한 명씩 대표를 뽑아 선택된 점수들의 최댓값과 최솟값의 차를 최소화하는 프로그램을 작성합니다.
난이도

보통10점 중 6점

유형
힙, 그리디, 정렬
정답자
아직 제출이 없습니다

문제

KOI 중학교에는 N개의 학급이 있고, 각 학급에는 M명의 학생이 있다. 모든 학생은 새 경기에서의 능력치를 하나씩 가지며, 모든 학생의 능력치는 서로 다르다.

각 학급에서 정확히 한 명씩 대표 선수를 뽑아 경기에 내보내려고 한다. 뽑힌 N명의 능력치 중 최댓값과 최솟값의 차이가 가능한 한 작아지도록 선수를 골라야 한다.

가능한 최솟값을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 학급의 수 N과 각 학급의 학생 수 M이 공백으로 구분되어 주어진다. 1 <= N, M <= 1,000이다.

다음 N개의 줄에는 각 학급 학생들의 능력치를 나타내는 M개의 정수가 공백으로 구분되어 주어진다. 각 능력치는 0 이상 10^9 이하이며, 모든 학생의 능력치는 서로 다르다.

출력

각 학급에서 한 명씩 뽑은 대표 선수들의 능력치 중 최댓값과 최솟값의 차이가 최소가 될 때, 그 차이를 정수 하나로 출력한다.

예제2

  1. 예제 1

    입력
    3 4
12 16 67 43
7 17 68 48
14 15 77 54
    예상 출력
    2

  2. 예제 2

    입력
    4 3
10 20 30
40 50 60
70 80 90
100 110 120
    예상 출력
    70