题面描述

给定按时间戳递增排序的数组sensor_$events$，其中每个元素为 [sensor_$id$, activation_$time$]。 定义：第$i$条记录对应的激活持续时间为当前记录时间戳与上一条记录时间戳之差，即 $d_i$ = activation_$time^{(i)}$ - activation_$time^{(i-1)}$，其中 activation_$time^{(0)}$ 视为实验开始时间$0$。 该持续时间归属于当前这一条记录的sensor_$id$。

要求返回两个sensor_$id$：

• 第一个是激活时间 最短 的传感器标识符（若并列取标识符最小者）
• 第二个是激活时间 最长 的传感器标识符（若并列取标识符最小者）

思路

1. 用一个变量$prev = 0$ 保存上一次事件的时间戳。

2. 依次读取每行 $[id, t]$：

   • 计算本次持续时间$dur = t - prev$

   • 用当前的$id$ 去更新“最短持续时间”与“最长持续时间”的候选：

     • 如果$dur$更小，或者$dur$相等但$id$更小，则更新最短
     • 如果$dur$ 更大，或者$dur$ 相等但$id$更小，则更新最长

   • 更新$prev = t$

3. 最终输出记录的两个sensor_$id$。

时间复杂度：$O(n)$，空间复杂度：$O(1)$（只需常数额外变量）

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    vector<pair<int,int>> events;
    int id, t;
    // 按行读取直到 EOF
    while (cin >> id >> t) {
        events.push_back({id, t});
    }
    if (events.empty()) return 0; // 无输入直接结束
    
    // 初始化
    int prev = 0; // 上一个时间戳
    long long minDur = LLONG_MAX, maxDur = LLONG_MIN;
    int minId = -1, maxId = -1;
    
    for (auto &e : events) {
        long long dur = e.second - prev; // 当前持续时间
        int curId = e.first;
        
        // 更新最短
        if (dur < minDur || (dur == minDur && curId < minId)) {
            minDur = dur;
            minId = curId;
        }
        // 更新最长
        if (dur > maxDur || (dur == maxDur && curId < maxId)) {
            maxDur = dur;
            maxId = curId;
        }
        prev = e.second;
    }
    
    cout << minId << " " << maxId << "\n";
    return 0;
}

Python

import sys
from math import inf

events = []
for line in sys.stdin:
    line = line.strip()
    if not line:
        continue
    a, b = map(int, line.split())
    events.append((a, b))

if not events:
    sys.exit(0)

prev = 0
min_dur, max_dur = inf, -inf
min_id, max_id = -1, -1

for sensor_id, t in events:
    dur = t - prev
    # 更新最短
    if dur < min_dur or (dur == min_dur and sensor_id < min_id):
        min_dur = dur
        min_id = sensor_id
    # 更新最长
    if dur > max_dur or (dur == max_dur and sensor_id < max_id):
        max_dur = dur
        max_id = sensor_id
    prev = t

print(min_id, max_id)

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        List<int[]> events = new ArrayList<>();
        while ((line = br.readLine()) != null) {
            line = line.trim();
            if (line.isEmpty()) continue;
            String[] parts = line.split("\\s+");
            int id = Integer.parseInt(parts[0]);
            int t  = Integer.parseInt(parts[1]);
            events.add(new int[]{id, t});
        }
        if (events.isEmpty()) return;
        
        int prev = 0;
        long minDur = Long.MAX_VALUE, maxDur = Long.MIN_VALUE;
        int minId = -1, maxId = -1;
        
        for (int[] e : events) {
            int curId = e[0];
            int curT  = e[1];
            long dur = (long)curT - prev;
            
            if (dur < minDur || (dur == minDur && curId < minId)) {
                minDur = dur;
                minId = curId;
            }
            if (dur > maxDur || (dur == maxDur && curId < maxId)) {
                maxDur = dur;
                maxId = curId;
            }
            prev = curT;
        }
        System.out.println(minId + " " + maxId);
    }
}

题目内容

假设你正在分析一批传感需记录的数据，这些数据记录了在某个实验或监测过程中各个传感器被激活的时间。这些数据储存在一个二维数组 $sensor$_$events$ 中。

数组 $sensor$ _$events$ 的每个元素 $sensor$ _$evenis[i]=[sensor$ _$id,activation$ _$time]$，其中 $sensor$ _$id$ 表示传感器的唯一标识符，而 $activation$ _$time$ 表示传感器被激活的时间戳。

数组 $sensor$ _$events$ 已经按照时间戳 $activatlon$ _$time$ 的递增顺序排列。每个传感器的激活持续时间定义为连续两次激活事件的时间差。第一个传感器的激活时间定义为从实验开始(默认为 $0$ )到第一次传感器被激活的时间差。一个传感器可能有多条激活数据，一个传感器的激活时间并不是固定的，所以有可能同一个传感器既是激活时间最长的，也是激活时间最短的。

你的任务是编写一个函数，返回 $2$ 个传感器的标识符 $sensor$ _$id$，分别表示激活时间最短的传感器和激活时间最长的传感器，如果有多个传感器的激活时间相同，那么取标识符最小的传感器。

输入描述

每一行代表数组 $sensor$ _$events$ 的元素 $sensor$ _$id$ 和 $acitvation$ _$time$，其中 $sensor$ _$id$ 表示传感器的唯一标识符，而 $acitvation$ _$time$ 表示传感器被激活的时间戳。每一行的 $sensor$ _$id$

和 $acitvation$ _$time$ 用空格隔开，每一行的$sensor$ _$id$ 在 $acitvation$ _$time$ 的前面。

参数范围：

$1<=sensor$ _$events.length <= 1000$

$sensor_events[i]=[sensor$ _$id,actwation$ _$time]$

$1<= sensor$ _$id, activatlon$ _$time <= 10^5$

输入保证数组 $sensor$ $_events$ 按照 $actvaton$ _$time$ 的动增顾产排序

输出描述

返回 $2$ 个 $sensor$ _$id$，分别表示激活时间最短的传感器和激活时间最长的传感器，用空格隔开。激活时间最短的传感器标识符放在激活时间最长的传感器标识符前面。如果有多个传感器的激活时间相同，那么取标识符最小的传感器。

样例1

输入

6 2
20 4
7 14
10 16

输出

6 7

说明

$sensor$ _$id$ 为 $6$ 的传感器的激活时间是 $2$ 。

$sensor$ _$id$为 $20$ 的传感器的激活时间是 $4-2=2$ 。

$sensor$ _$id$为 $7$ 的传感器的激活时间是 $14-4=10$ 。

$sensor$ _$id$为 $10$ 的传感器的激活时间是 $16-14=2$ 。

最终，$sensor$ _$id$ 为 $6、20、10$ 的激活时间相同，都是 $2$ ，但 $6<10<20$ ，$6$ 最小，所以取 $sensor$ _$id$ 为 $6$ 的传感器作为激活时间最短的传感器，$sensor$ _$id$ 为 $7$ 的传感器的激活时间最长，输出 $6$ $7$

样例2

输入

9 6
2 7
9 9
10 12

输出

2 9

说明

$sensor$ _$id$ 为 $9$ 的传感器的激活时间是 $6$ 。

$sensor$ _$id$为 $2$ 的传感器的激活时间是 $7-6=1$ 。

$sensor$ _$id$为 $9$ 的传感器的激活时间是 $9-7=2$ 。

$sensor$ _$id$为 $10$ 的传感器的激活时间是 $12-9=3$ 。

最终，$sensor$ _$id$ 为 $2$ 的激活时间为 $1$ ，$sensor$ _$id$ 为 $9$ 的传感器的激活时间有 $2$ 和 $6$ ，$sensor$ _$id$ 为 $10$ 的传感器的激活时间有 $3$ ，所有 $sensor$ _$id$ 为 $2$ 的传感器有最短的激活时间 $1$ ，$sensor$ _$id$ 为 $9$ 的传感器有最长的激活时间 $6$ ，输出为 $2$ $9$