题目描述

某设备需要记录每分钟检测到的指标值。为了节约存储空间，将连续相同指标值的记录合并。

压缩之前： 202411231000,11 202411231001,11 202411231002,12 202411231003,12 202411231004,10 202411231005,17 202411231006,17 202411231007,17

压缩之后： 202411231000,202411231001,11 202411231002,202411231003,12 202411231004,202411231004,10 202411231005,202411231007,17

查询时，根据输入的时间范围进行查询，需要返回回时间范围内记录的每分钟的指标值，如果某个时间点没有记录值，则此条记录忽略不返回。

输入描述

第一行为查询的时间范围，格式是：startTime,endTime。查询的时间范围为闭区间，即大于等于startTime且小于等于endTime， startTime <= endTime，且他们跨度的分钟数小于100；

第二行为压缩日志记录的行数，100 >= N > 0；

第三行及以后为压缩日志内容。每一行的格式为：startTime,endTime,kpi，其中 startTime<=endTime，10^5>kpi>=0；记录已按升序进行排序。

不保证两行记录之间是紧密连接，startTime和endTime的时间跨度可能很大。 如：上一行的数据显示范围是202411231540, 202411231542，下一行的数据显示可以是 202411231544, 202411231547， 中间202411231543的数据可能由于其他原因缺失。

输出描述

输出描述 查询到的日志清单，如： 202411231010,11 202411231011,10 202411231012,10 202411231013,16

输出结果按数据时间升序排序。

补充说明 输入的数据可能超出当前已存储的数据范围，此时只输出查询到的数据。 如果从头到尾都没有查询到记录，则输出-1。

用例1

输入

202411231010,202411231013

4

202411231000,202411231010,11

202411231011,202411231012,10

202411231013,202411231020,16

202411231021,202411231028,17

输出

202411231010,11

202411231011,10

202411231012,10

202411231013,16

说明

202411231010时间的指标值在202411231000,202411231010范围内，值是11 202411231011,202411231012时间的指标值在202411231011,202411231012范围内，值是10 202411231013时间的指标值在202411231013,202411231020范围内，值是16

问题分析

题目要求处理压缩后的时间序列数据，并根据查询范围恢复每分钟的原始数据。压缩数据格式为startTime,endTime,value，表示从startTime到endTime（闭区间）每分钟的指标值均为value。查询时需要将压缩数据解压为每分钟的记录，并筛选出落在查询时间范围内的记录。

解决思路

1. 解析查询范围：获取查询的起始时间和结束时间。
2. 处理压缩数据：遍历每条压缩记录，检查其时间范围是否与查询范围有交集。
3. 生成每分钟记录：对于有交集的压缩记录，生成每分钟的记录，并筛选出落在查询范围内的记录。
4. 合并和排序结果：将所有符合条件的记录按时间升序排序后输出。

代码实现

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Record {
    long long time;
    int value;
};

bool compareRecords(const Record &a, const Record &b) {
    return a.time < b.time;
}

int main() {
    long long startQuery, endQuery;
    char comma;
    cin >> startQuery >> comma >> endQuery;
    
    int n;
    cin >> n;
    
    vector<Record> records;
    
    for (int i = 0; i < n; ++i) {
        long long start, end;
        int value;
        cin >> start >> comma >> end >> comma >> value;
        
        long long overlapStart = max(start, startQuery);
        long long overlapEnd = min(end, endQuery);
        
        if (overlapStart <= overlapEnd) {
            for (long long t = overlapStart; t <= overlapEnd; ++t) {
                records.push_back({t, value});
            }
        }
    }
    
    if (records.empty()) {
        cout << -1 << endl;
    } else {
        sort(records.begin(), records.end(), compareRecords);
        for (const auto &record : records) {
            cout << record.time << "," << record.value << endl;
        }
    }
    
    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    long long time;
    int value;
} Record;

int compareRecords(const void *a, const void *b) {
    Record *ra = (Record *)a;
    Record *rb = (Record *)b;
    return (ra->time > rb->time) - (ra->time < rb->time);
}

int main() {
    long long startQuery, endQuery;
    scanf("%lld,%lld", &startQuery, &endQuery);
    
    int n;
    scanf("%d", &n);
    
    Record *records = malloc(100 * sizeof(Record));
    int count = 0;
    
    for (int i = 0; i < n; ++i) {
        long long start, end;
        int value;
        scanf("%lld,%lld,%d", &start, &end, &value);
        
        long long overlapStart = start > startQuery ? start : startQuery;
        long long overlapEnd = end < endQuery ? end : endQuery;
        
        if (overlapStart <= overlapEnd) {
            for (long long t = overlapStart; t <= overlapEnd; ++t) {
                records[count].time = t;
                records[count].value = value;
                count++;
            }
        }
    }
    
    if (count == 0) {
        printf("-1\n");
    } else {
        qsort(records, count, sizeof(Record), compareRecords);
        for (int i = 0; i < count; ++i) {
            printf("%lld,%d\n", records[i].time, records[i].value);
        }
    }
    
    free(records);
    return 0;
}

Python

start_query, end_query = map(int, input().split(','))
n = int(input())

records = []

for _ in range(n):
    start, end, value = map(int, input().split(','))
    overlap_start = max(start, start_query)
    overlap_end = min(end, end_query)
    if overlap_start <= overlap_end:
        for t in range(overlap_start, overlap_end + 1):
            records.append((t, value))

if not records:
    print(-1)
else:
    records.sort()
    for t, value in records:
        print(f"{t},{value}")

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] queryRange = scanner.nextLine().split(",");
        long startQuery = Long.parseLong(queryRange[0]);
        long endQuery = Long.parseLong(queryRange[1]);
        
        int n = Integer.parseInt(scanner.nextLine());
        
        List<Record> records = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            String[] parts = scanner.nextLine().split(",");
            long start = Long.parseLong(parts[0]);
            long end = Long.parseLong(parts[1]);
            int value = Integer.parseInt(parts[2]);
            
            long overlapStart = Math.max(start, startQuery);
            long overlapEnd = Math.min(end, endQuery);
            
            if (overlapStart <= overlapEnd) {
                for (long t = overlapStart; t <= overlapEnd; t++) {
                    records.add(new Record(t, value));
                }
            }
        }
        
        if (records.isEmpty()) {
            System.out.println(-1);
        } else {
            records.sort(Comparator.comparingLong(Record::getTime));
            for (Record record : records) {
                System.out.println(record.getTime() + "," + record.getValue());
            }
        }
    }
    
    static class Record {
        private long time;
        private int value;
        
        public Record(long time, int value) {
            this.time = time;
            this.value = value;
        }
        
        public long getTime() {
            return time;
        }
        
        public int getValue() {
            return value;
        }
    }
}

JavaScript

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let lines = [];
rl.on('line', (line) => {
    lines.push(line);
}).on('close', () => {
    const [startQuery, endQuery] = lines[0].split(',').map(Number);
    const n = parseInt(lines[1]);
    
    let records = [];
    
    for (let i = 2; i < 2 + n; i++) {
        const [start, end, value] = lines[i].split(',').map(Number);
        const overlapStart = Math.max(start, startQuery);
        const overlapEnd = Math.min(end, endQuery);
        
        if (overlapStart <= overlapEnd) {
            for (let t = overlapStart; t <= overlapEnd; t++) {
                records.push({ time: t, value: value });
            }
        }
    }
    
    if (records.length === 0) {
        console.log(-1);
    } else {
        records.sort((a, b) => a.time - b.time);
        for (const record of records) {
            console.log(`${record.time},${record.value}`);
        }
    }
});

代码解释

• 输入处理：读取查询范围和压缩数据行数，然后逐行读取压缩数据。
• 时间范围交集计算：对于每条压缩数据，计算其与查询范围的重叠部分。
• 记录生成：在重叠时间范围内生成每分钟的记录，并存储到列表中。
• 结果输出：如果列表为空，输出-1；否则对记录按时间排序后逐条输出。

每种语言的实现逻辑相同，只是语法和数据结构略有差异。