当前位置: 面试刷题>> 会议室 (经典算法题500道)


题目描述补充

题目:会议室预订系统

在一个公司中,有多个会议室可用于不同的会议。每个会议都有一个开始时间和一个结束时间,且会议时间不能重叠使用同一个会议室。给定一系列会议的开始时间和结束时间(假设都是同一天内),设计一个算法来找出最小的会议室数量,使得所有会议都能被安排。

示例

输入:[[10, 30], [20, 40], [15, 25], [5, 15]]

输出:3

解释:第一个会议从10点到30点,第二个会议从20点到40点,第三个会议从15点到25点,第四个会议从5点到15点。我们可以将第一个会议安排在第一个会议室,第二个会议安排在第二个会议室,第三个会议和第四个会议时间上有重叠,但第三个会议可以在第一个会议结束后立即开始,所以只需要第三个会议室来安排第三个和第四个会议(第四个会议在第一个会议室结束后开始,并且在其结束前第三个会议室已经空闲)。因此,总共需要3个会议室。

PHP 示例代码

function minMeetingRooms($intervals) {
    if (empty($intervals)) {
        return 0;
    }

    // 按照会议的开始时间进行排序
    usort($intervals, function($a, $b) {
        return $a[0] - $b[0];
    });

    $rooms = 1; // 至少需要一个会议室
    $endTimes = [$intervals[0][1]]; // 记录每个会议室的结束时间

    // 遍历每个会议
    for ($i = 1; $i < count($intervals); $i++) {
        // 查找最早结束的会议室
        $earliestEndTime = min($endTimes);

        // 如果当前会议的开始时间小于等于最早结束的会议室的结束时间
        // 则需要一个新的会议室
        if ($intervals[$i][0] <= $earliestEndTime) {
            $rooms++;
        }

        // 更新最早结束的会议室的结束时间为当前会议的结束时间
        // 使用二分查找优化这里可以进一步提升性能,但为简洁明了,这里使用简单遍历
        $keyToRemove = array_search($earliestEndTime, $endTimes);
        unset($endTimes[$keyToRemove]);
        $endTimes[] = $intervals[$i][1];
    }

    return $rooms;
}

// 示例使用
$intervals = [[10, 30], [20, 40], [15, 25], [5, 15]];
echo minMeetingRooms($intervals); // 输出: 3

Python 示例代码

def minMeetingRooms(intervals):
    if not intervals:
        return 0

    # 按开始时间排序
    intervals.sort(key=lambda x: x[0])

    rooms = 1
    end_times = [intervals[0][1]]

    for i in range(1, len(intervals)):
        if intervals[i][0] < min(end_times):
            rooms += 1
        # 二分查找优化查找最早结束的会议室并更新
        # 这里简单处理为移除最早结束的并添加新的结束时间
        end_times.remove(min(end_times))
        end_times.append(intervals[i][1])

    return rooms

# 示例使用
intervals = [[10, 30], [20, 40], [15, 25], [5, 15]]
print(minMeetingRooms(intervals))  # 输出: 3

JavaScript 示例代码

function minMeetingRooms(intervals) {
    if (intervals.length === 0) {
        return 0;
    }

    // 按开始时间排序
    intervals.sort((a, b) => a[0] - b[0]);

    let rooms = 1;
    let endTimes = [intervals[0][1]];

    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] <= Math.min(...endTimes)) {
            rooms++;
        }

        // 找到并移除最早结束的会议室
        let minEnd = Math.min(...endTimes);
        endTimes = endTimes.filter(time => time !== minEnd);

        // 添加新的结束时间
        endTimes.push(intervals[i][1]);
    }

    return rooms;
}

// 示例使用
const intervals = [[10, 30], [20, 40], [15, 25], [5, 15]];
console.log(minMeetingRooms(intervals)); // 输出: 3

码小课网站中有更多相关内容分享给大家学习,包括算法优化、数据结构等进阶知识。

推荐面试题