一、题目

1
2
3
4
5
6
7
8
9
10
现有若干个会议，所有会议共享一个会议室，用数组表示各个会议的开始时间和结束时间，

格式为： 
[[会议1开始时间, 会议1结束时间], [会议2开始时间, 会议2结束时间]] 

请计算会议室占用时间段。

会议室个数范围：[1, 100]
会议室时间段：[1, 24]

二、输入

1
2
3
第一行输入一个整数n，表示会议数量 

之后输入n行，每行两个整数，以空格分隔，分别表示会议开始时间，会议结束时间

三、输出

1
输出多行，每个两个整数，以空格分隔，分别表示会议室占用时间段开始和结束

四、示例

1
2
3
4
5
6
7
8
9
10
11
输入：
4
1 4
2 5
7 9
14 18

输出：
1 5
7 9
14 18

五、题解

区间合并问题。注意按起点排序。

5.1 Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package org.stone.study.algo.ex202411;

import java.util.*;

/**
 * 会议室安排: 合并重叠的区间
 */
public class MeetingRoom {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 4
        int m = scanner.nextInt();
        // 1 4
        // 2 5
        // 7 9
        // 14 18
        int[][] intervals = new int[m][2];
        for(int i = 0; i < m; i++) {
            intervals[i][0] = scanner.nextInt();
            intervals[i][1] = scanner.nextInt();
        }

        int[][] res = merge(intervals);
        // 1 5
        // 7 9
        // 14 18
        Arrays.stream(res).forEach(e -> System.out.println(e[0] + " " + e[1]));
    }

    /**
     * 合并重叠区间
     * @param intervals
     * @return
     */
    public static int[][] merge(int[][] intervals) {
        if(intervals == null || intervals.length == 0) {
            return new int[0][0];
        }
        // 按区间左端点升序排序
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        List<int[]> res = new ArrayList<>();
        int m = intervals.length;
        int[] cur = intervals[0];
        res.add(cur);
        for(int i = 1; i < m; i++) {
            int[] next = intervals[i];
            if(cur[1] >= next[0]) {
                // 合并区间
                cur[1] = Math.max(cur[1], next[1]);
            } else {
                // 不重叠，更新 cur，增加一条新的区间
                cur = next;
                res.add(cur);
            }
        }

        return res.toArray(new int[res.size()][]);
    }
}

5.2 Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        # 新增一条区间
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            # 合并区间（更新上一条区间的右端点）
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

if __name__ == "__main__":
    # 4
    m = int(input())
    # 输入 m 行，每行两个数字，表示一个区间
    # 1 3
    # 2 6
    # 8 10
    # 15 18
    intervals = [list(map(int, input().split())) for _ in range(m)]

    ans = merge_intervals(intervals)

    # 按行打印结果
    for interval in ans:
        print(interval[0], interval[1])