Java 中所需会议室的最小数量问题

这是一个非常有趣的问题，经常出现在 Google、Amazon、TCS、Accenture、Adobe、Apple、Infosys 等顶级 IT 公司的面试中。通过解决这个问题，面试官希望检查面试者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将使用不同的方法和逻辑来 在 Java 中找到所需会议室的最少数量问题。此外，我们还将为此创建 Java 程序。

问题陈述

在这个问题中，我们得到了一个会议时间间隔的数组（开始时间和结束时间）。我们必须找到 所需会议室的最少数量。

示例

假设，给定的会议开始和结束时间数组为 { { 1, 20 }, { 19, 30}, { 40, 70 } }。

让我们为每个间隔分配一个房间。将房间 1 分配给第一个间隔 (1, 20)。第二个间隔在第一个间隔进行时开始，因此将房间 2 分配给第二个间隔 (19, 30)。第三个间隔在第二个间隔之后开始。因此，将房间 2 分配给第三个间隔 (40, 70)。因此，我们总共需要 两个 会议室。

让我们看另一个例子。

首先，我们将使用优先队列或按时间顺序排列数组来解决这个问题。

{ { 1, 18 }, { 18, 23 }, { 15, 29 }, {4, 15}, {2, 11}, {5, 13} }

创建两个数组来存储间隔（会议开始和结束时间）。

开始时间 = {1, 18, 15, 4, 2, 5}

结束时间 = {18, 23, 29, 15, 11, 13}

为了更好地理解，我们将创建一个时间间隔表。

现在，我们将迭代这两个数组。检查开始数组中的元素是否小于结束数组中的元素。如果条件返回 true，则创建一个新房间并分配该时间间隔。之后，继续处理开始时间数组中的下一个元素。

另一方面，如果结束元素小于开始元素，我们则寻找一个现有的会议室。一旦完成，我们将两个行中的指针都向前移动一位。

因此，

会议 一 可以在会议室 1 中从 1 - 18 进行。

会议 五 可以在会议室 2 中从 2 - 11 进行。

会议 四 可以在会议室 3 中从 4 - 15 进行。

会议 六 可以在会议室 4 中从 5 - 13 进行。

会议 三 可以在会议室 2 中从 15 - 29 进行，因为它在此间隔内是空闲的。

会议 二 可以在会议室 4 中从 18 - 23 进行，因为它在此间隔内是空闲的。

问题解决方案

首先，创建两个排序后的数组。第一个数组表示会议开始时间，第二个数组表示会议结束时间。定义两个变量，分别用于迭代开始和结束数组，例如 i 和 j。定义另一个名为 curr 的变量，它将计算当前正在进行的会议数量。

• 如果条件 start[i] < end[j] 变为 true，这意味着第 j 次会议正在进行，我们需要另一个会议室用于第 i 次会议。将变量 curr 和 i 增加一，因为我们已经开始了 第 i 次 会议。
• 如果条件 start[i] >= end[j] 变为 true，这意味着第 j 次会议已经结束，该房间现在空闲，将变量 curr 减少一，并将变量 j 增加一，因为 第 j 次 会议已经结束。

现在我们的答案是整个过程中变量 curr 的最高值。

Java 程序查找所需会议室的最少数量

MeetingRoom1.java

输出

Total Number of Meeting room required is: 4

让我们看看解决相同问题的另一种方法。

我们首先根据开始时间对时间间隔进行排序，有一个计数器，通过将结束时间添加到优先队列中来比较每个开始时间和相应的结束时间。如果开始时间较小，则增加计数器，否则从队列中弹出结束时间。

让我们在 Java 程序中实现这种方法。

MeetingRoom2.java

输出

Minimum number of meeting rooms required is 2

复杂度

由于数组排序，上述方法的时间复杂度为 O(nlogn)。上述方法的空间复杂度为 O(n)。