Optiver 25 ng | Optiver oa questions | 一亩三分地 | OA代写

class LogServer:
    def __init__(self, m):
        self.logs_dict = {}  # 存储日志ID及其时间戳
        self.m = m  # 最大日志数量限制
        self.log_ids_queue = []  # 保存最近m个日志ID的队列

    def recordLog(self, logId, timestamp):
        # 更新日志ID的时间戳
        if logId in self.logs_dict:
            self.logs_dict[logId].append(timestamp)
        else:
            self.logs_dict[logId] = [timestamp]

        # 更新日志ID队列
        while len(self.log_ids_queue) >= self.m:
            oldest_log_id = self.log_ids_queue.pop(0)
            del self.logs_dict[oldest_log_id]

        self.log_ids_queue.append(logId)

    def getLogs(self):
        # 返回最近一小时内的最新m个日志ID
        current_time = time.time()
        one_hour_ago = current_time - 3600

        sorted_logs = sorted(
            self.logs_dict.items(),
            key=lambda x: (x[1][-1], self.logs_dict[x[0]][-1])
        )
        recent_logs = [
            logId for logId, timestamps in sorted_logs
            if timestamps[-1] > one_hour_ago
        ]

        return ",".join(str(logId) for logId in recent_logs[:self.m])

    def getLogCount(self):
        # 返回最近一小时内的日志总数
        current_time = time.time()
        one_hour_ago = current_time - 3600

        return sum(
            len(timestamps)
            for logId, timestamps in self.logs_dict.items()
            if timestamps[-1] > one_hour_ago
        )

import heapq

class Scheduler:
    def __init__(self, processes, dependencies):
        self.processes = {pid: (start, end) for pid, start, _ in processes}
        self.dependencies = dependencies
        self.in_degrees = {
            pid: 0 for pid in range(1, max(self.processes.keys())+1)
        }
        for dep in dependencies:
            self.in_degrees[dep[1]] += 1
        self.schedule = []

    def PrintSchedule(self):
        self.topological_sort()
        earliest_start = min(p[0] for p in self.processes.values())
        latest_end = max(p[1] for p in self.processes.values())
        duration = latest_end - earliest_start
        print(*sorted(pid for pid in self.schedule), sep=" ")

    def topological_sort(self):
        queue = []
        for pid, (_, end) in self.processes.items():
            if self.in_degrees[pid] == 0:
                heapq.heappush(queue, (-end, pid))
        while queue:
            _, pid = heapq.heappop(queue)
            self.schedule.append(pid)
            for dependent in self.dependencies.get(pid, []):
                self.in_degrees[dependent] -= 1
                if self.in_degrees[dependent] == 0:
                    heapq.heappush(
                        queue, (-self.processes[dependent][1], dependent)
                    )

    @staticmethod
    def read_input():
        n_p, n_d = map(int, input().split())
        processes = [tuple(map(int, input().split())) for _ in range(n_p)]
        dependencies = [tuple(map(int, input().split())) for _ in range(n_d)]
        return processes, dependencies

    def run_all_test_cases(self):
        t = int(input())
        for _ in range(t):
            processes, dependencies = self.read_input()
            Scheduler(processes, dependencies).PrintSchedule()

if __name__ == "__main__":
    Scheduler([], []).run_all_test_cases()