本文共 1392 字，大约阅读时间需要 4 分钟。
为了解决这个问题，我们需要找到最少需要的站台数量，使得所有火车能够按时进站和出站，而不会有任何时间段冲突。
问题分析：每辆火车需要一个连续的时间段来停靠。我们需要确保在任何时候，同一站台不会有多辆火车停靠。因此，我们需要找出这些时间段中最大的重叠情况，从而确定最少需要多少个站台。
贪心算法：我们可以使用贪心算法来解决这个问题。具体步骤如下：
时间复杂度：排序操作的时间复杂度为 (O(n \log n))，遍历操作的时间复杂度为 (O(n))，因此总的时间复杂度为 (O(n \log n))。
def main(): import sys input = sys.stdin.read().split() ptr = 0 T = int(input[ptr]) ptr += 1 for _ in range(T): n = int(input[ptr]) ptr += 1 trains = [] for _ in range(n): s = int(input[ptr]) t = int(input[ptr+1]) ptr += 2 trains.append((s, t)) if n == 0: print(0) continue trains.sort() current_end = trains[0][1] count = 1 for i in range(1, n): if trains[i][0] > current_end: count += 1 current_end = trains[i][1] else: current_end = max(current_end, trains[i][1]) print(count)if __name__ == "__main__": main()
sys.stdin.read() 读取所有输入数据，并将其拆分成列表处理。该方法确保了在任何时候，同一站台不会有多辆火车停靠，从而找到最少需要的站台数量。
转载地址：http://ztlxz.baihongyu.com/