字节跳动 2021 春招面试高频题3_字节跳动2021春招笔试

描述

给定一系列的会议时间间隔intervals，包括起始和结束时间[[s1,e1],[s2,e2],…] (si < ei)，找到所需的最小的会议室数量。

案例

样例1

输入: intervals = [(0,30),(5,10),(15,20)]
输出: 2
解释:
需要两个会议室
会议室1:(0,30)
会议室2:(5,10),(15,20)

样例2
输入: intervals = [(2,7)]
输出: 1
解释:
只需要1个会议室就够了
1
2
3
4
5
6
7
8
9
10
11
12
13
14

解析

我们来看一下这道题，你仔细想一下，虽然题的描述是“所需的最小的会议室数量”。但是你细想，再细想，其实是你需要的最大的会议室数量。因为当你需要最大3个会议室的时候，就说明这道题的答案是3，也就是所求的最小的会议室数量。你细品。

我们这里用的方法叫做扫描线方法，就是每一个时间的interval，开始是会议开始的时间，第二个是会议结束的时间。那你是不是可以重新生成一个类，然后里面有一个表示是开会还是结束的Flag。然后按照这个时间来排序，从前到后，开会就+1，结束就-1。然后最大的那个数字就是你需要的会议室。

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class MeetingRoom{
    
    class Meeting {
        int time;
        boolean onOffMeeting;
        public Meeting(int time, boolean onOffMeeting) {
            this.time = time;
            this.onOffMeeting = onOffMeeting;
        }
    }
    /**
     * @param intervals: an array of meeting time intervals
     * @return: the minimum number of conference rooms required
     */
    public int minMeetingRooms(List<Interval> intervals) {
        // Write your code here
        if (intervals == null || intervals.size() == 0) {
            return 0;
        }
        List<Meeting> meetings = new ArrayList<>();
        for (Interval interval: intervals) {
            Meeting meeting1 = new Meeting(interval.start, true);
            Meeting meeting2 = new Meeting(interval.end, false);
            meetings.add(meeting1);
            meetings.add(meeting2);
        }
        
        Collections.sort(meetings, new Comparator<Meeting>(){
            
            public int compare(Meeting meeting1, Meeting meeting2) {
                return meeting1.time - meeting2.time;
            }
        });
        
        int meetRooms = 0;
        int minRooms = 0;
        for (Meeting meeting: meetings) {
            if (meeting.onOffMeeting) {
                meetRooms++;
            } else {
                meetRooms--;
            }
            minRooms = Math.max(minRooms, meetRooms);
        }
        return minRooms;
    }
}
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