题解 | #最小区间#

#include<bits/stdc++.h>
using namespace std;

// 定义节点结构
struct node {
    int x, type;  // x为值，type为数组编号
    node(int x, int type):x(x),type(type){}
};

// 定义优先队列的比较函数
struct cmp {
    bool operator()(const node& a, const node& b)const {
        return a.x > b.x;
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int k, n;
    cin >> k >> n;
    
    // 存储所有数组，下标从1开始
    vector<vector<int>> a(k+1, vector<int>(n+1));
    for(int i = 1; i <= k; ++i) {
        for(int j = 1; j <= n; ++j) {
            cin >> a[i][j];
        }
    }
    
    priority_queue<node, vector<node>, cmp> px;
    
    // 初始化：取每个数组的第一个元素
    int mi = a[1][1], ma = a[1][1];
    for(int i = 1; i <= k; ++i) {
        a[i][0] = 1;  // 记录当前位置
        node tmp = {a[i][1], i};
        px.push(tmp);
        mi = min(mi, tmp.x);
        ma = max(ma, tmp.x);
    }
    
    int maa = ma;  // 维护当前最大值
    
    // 当优先队列中元素个数等于k时继续
    while(px.size() == k) {
        node tmp = px.top();
        px.pop();
        int type = tmp.type;
        
        // 如果当前数组还有元素
        if(a[type][0] < n) {
            node add = {a[type][++a[type][0]], type};
            px.push(add);
            int mii = px.top().x;
            maa = max(maa, add.x);
            
            // 更新最优区间
            if(maa - mii < ma - mi) {
                mi = mii;
                ma = maa;
            }
        }
    }
    
    cout << mi << " " << ma << endl;
    return 0;
}

import java.util.*;

class Node {
    int x, type;
    Node(int x, int type) {
        this.x = x;
        this.type = type;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int n = sc.nextInt();
        
        int[][] a = new int[k+1][n+1];
        int[] pos = new int[k+1];  // 记录每个数组的当前位置
        
        // 读入数据
        for(int i = 1; i <= k; i++) {
            for(int j = 1; j <= n; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        
        // 创建优先队列
        PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> x.x - y.x);
        
        // 初始化
        int mi = a[1][1], ma = a[1][1];
        for(int i = 1; i <= k; i++) {
            pos[i] = 1;
            Node node = new Node(a[i][1], i);
            pq.offer(node);
            mi = Math.min(mi, node.x);
            ma = Math.max(ma, node.x);
        }
        
        int maa = ma;
        
        while(pq.size() == k) {
            Node curr = pq.poll();
            int type = curr.type;
            
            if(pos[type] < n) {
                Node next = new Node(a[type][++pos[type]], type);
                pq.offer(next);
                int mii = pq.peek().x;
                maa = Math.max(maa, next.x);
                
                if(maa - mii < ma - mi) {
                    mi = mii;
                    ma = maa;
                }
            }
        }
        
        System.out.println(mi + " " + ma);
    }
}

from heapq import *

class Node:
    def __init__(self, x, type):
        self.x = x
        self.type = type
    
    def __lt__(self, other):
        return self.x < other.x

k = int(input())
n = int(input())
a = [[0] * (n+1) for _ in range(k+1)]
pos = [1] * (k+1)  # 记录每个数组的当前位置

# 读入数据
for i in range(1, k+1):
    row = list(map(int, input().split()))
    for j in range(1, n+1):
        a[i][j] = row[j-1]

# 初始化优先队列
pq = []
mi = ma = a[1][1]

for i in range(1, k+1):
    node = Node(a[i][1], i)
    heappush(pq, node)
    mi = min(mi, node.x)
    ma = max(ma, node.x)

maa = ma

while len(pq) == k:
    curr = heappop(pq)
    type = curr.type
    
    if pos[type] < n:
        pos[type] += 1
        next_node = Node(a[type][pos[type]], type)
        heappush(pq, next_node)
        mii = pq[0].x
        maa = max(maa, next_node.x)
        
        if maa - mii < ma - mi:
            mi = mii
            ma = maa

print(mi, ma)