我碰到了这个问题，我不确定我的解决方案是否是最佳的。
给定N加权(Wi)和可能重叠的间隔(代表会议日程)，找出召开所有会议所需的最小会议室数量"&"容量。
|---10------|. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .|---------8---------|
|------8-----| |----------10-----------|
|--------6-------|
|---10------|. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .|---------8---------|
|------8-----| |----------10-----------|
|--------6-------|
按照上述日程安排，我们需要两间可容纳10人和10人的会议室。(我说的对吗?)
我的解决方案取一组房间，从左边遍历间隔，如果我们有一个容量大于需要的会议室，使用它，如果没有符合标准的会议室，建立一个新的房间或增加现有的房间与新的容量。
的例子:
Start of 10 - {10}
8 - {10,8}
End of 10- {10-free, 8}
6 - {10,8}
End of 8- {10,8 -free}
起始点= {10,8 +=2}OR {10,10}
等.....
这实际上是贪婪的…
- 有人能证明这不是最优的吗?
- 如果这不是最优的解决方案是什么?DP ?
我认为这个问题相当于"铁路/汽车站所需的最小站台数"问题。
这篇文章http://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/很好地解释了如何处理它。
Intuition
我要试一试。幼稚的方法是列举所有可能的解决方案，然后选出最好的一个。考虑到这一点，找到可以容纳n会议的k房间相当于找到n点的k路分区。5会议的2 -way分区的示例为OP示例中的[ 0,2,4 ]和[ 1,3 ]:
|---0------| |---------4---------|
|------1-----| |----------3-----------|
|--------2-------|
因此，基本思想是枚举n会议的所有k -way分区，并约束两个重叠的会议不能属于同一个集群。例如，[ 0,1,2 ]和[ 3,4 ]不是一个有效的分区，因为会议[ 0,1,2 ]不能在房间里举行;会议[ 3,4 ]也是如此。幸运的是，当使用递归方法时，该约束很容易实现。
对于Python，它看起来像这样:
def kWay( A, k, overlap ) :
"""
A = list of meeting IDs, k = number of rooms,
overlap[ meeting ID m ] = set of meetings overlapping with m
"""
if k == 1 : # only 1 room: all meetings go there
yield [ A[:] ]
elif k == len(A) : # n rooms and n meetings: put 1 meeting per room
yield [ [a] for a in A ]
else :
for partition in kWay( A[1:], k, overlap ) : # add new meeting to one existing room
for i, ci in enumerate( partition ) :
isCompatible = all( A[0] not in overlap[x] for x in ci ) # avoid 2 overlapping meetings in the same room
res = partition[:i] + [ ci + [ A[0] ] ] + partition[ i+1: ]
if isCompatible :
yield res
for partition in kWay( A[1:], k-1, overlap ) : # add new meeting to a new room
isValid = ( set(A[1:]) & set.union( * ( overlap[a] for a in A[ 1: ] ) ) == set() ) # avoid 2 overlapping meetings in the same room
if (k-1>1) or ( k-1==1 and isValid ) :
yield partition + [ [ A[0] ] ]
这看起来有点复杂，但当你意识到它只是k方式分区的递归算法+ 2额外的行来保证我们只考虑有效的分区时，它实际上非常简单。
OP示例解
好的，现在让我们使用OP示例准备输入数据:
import collections
n = 5
k = 2
#
A = range(n)
# prepare overlap dictionary
pairs = [ (0,1), (1,2), (2,3), (3,4) ] # overlapping meetings
size = dict( ( (0,10), (1,8), (2,6) , (3,10), (4,8) ) )
overlap = collections.defaultdict(set)
for (i,j) in pairs :
overlap[i].add(j)
overlap[j].add(i)
defaultdict(<type 'set'>, {0: set([1]), 1: set([0, 2]), 2: set([1, 3]), 3: set([2, 4]), 4: set([3])})
{0: 10, 1: 8, 2: 6, 3: 10, 4: 8}
现在我们只遍历有效的2 -way分区并打印房间大小。只有一个有效分区，所以这是我们的解决方案:
for partition in kWay( A, k, overlap ) :
print partition, [ max( size[x] for x in c ) for c in partition ]
[[3, 1], [4, 2, 0]] [10, 10]
好的，1,3会议在10会议室举行，0,2,4会议在10会议室举行。
一个稍微复杂一点的例子
但是只有一个有效的2 -way分区，所以这当然也是最优解。多么无聊啊!让我们在OP示例中添加一个新的会议5和一个新的房间，以使其更有趣:
|---0------| |---5---| |---------4---------|
|------1-----| |----------3-----------|
|--------2-------|
对应的输入数据:
n = 6
k = 3
#
A = range(n)
pairs = [ (0,1), (1,2), (2,3), (3,4), (5,2), (5,3) ] # overlapping meetings
size = dict( ( (0,10), (1,8), (2,6) , (3,10), (4,8), (5,2) ) )
overlap = collections.defaultdict(set)
for (i,j) in pairs :
overlap[i].add(j)
overlap[j].add(i)
defaultdict(<type 'set'>, {0: set([1]), 1: set([0, 2]), 2: set([1, 3, 5]), 3: set([2, 4, 5]), 4: set([3]), 5: set([2, 3])})
{0: 10, 1: 8, 2: 6, 3: 10, 4: 8, 5: 2}
和结果:
for partition in kWay( A, k, overlap ) :
print partition, [ max( size[x] for x in c ) for c in partition ]
[[3, 1], [4, 2, 0], [5]] [10, 10, 2]
[[3, 1], [4, 2], [5, 0]] [10, 8, 10]
[[3, 0], [4, 2], [5, 1]] [10, 8, 8]
[[3], [4, 2, 0], [5, 1]] [10, 10, 8]
[[4, 5, 1], [3, 0], [2]] [8, 10, 6]
[[4, 5, 1], [3], [2, 0]] [8, 10, 10]
[[4, 5, 0], [3, 1], [2]] [10, 10, 6]
[[4, 5], [3, 1], [2, 0]] [8, 10, 10]
最优3路分区为[[3, 1], [4, 2, 0], [5]]，最优房间大小为[10, 10, 2]。您也可以直接获得所有房间的最小尺寸:
min( sum( [ max( size[x] for x in c ) for c in partition ] ) for partition in kWay( A, k, overlap ) )
22
考虑这个场景:
(m1) |-3-|
(m2) |--2--|
(m3) |--1--|
(m4) |-1-|
(m5) |-2-|
您的解决方案将继续如下:
- {3}(第一个房间创建)
- {3,2}(同时开两场会议，需要第二个房间)
- {3,2,1}(同时召开三次会议，需要第三间会议室)
- {3,2,1} (m1结束，所以m4进入3个房间)
- {3,2,1,2}(同时召开四次会议，需要第四个会议室，创建与最新会议相同大小的会议室)
该方案的累计容量为8。
现在考虑这个解:{3,2,1,1}。它的累积容量为7。
在上面的步骤(4)中，m4将进入未占用的1号房间，而3号房间仍然是打开的。因此，这就是m5要去的地方。
假设
- 最优解决方案首先按房间数量排序:它将拥有最少数量的房间。第二个标准是，它会这样做具有最低的累积容量:的容量之和每个房间。
- 当你的解决方案被识别为贪婪时要创建一个房间，您将创建一个房间的大小评估。
- 两个会议不能同时在一个房间举行，无论大小。
算法修改
Update:我刚刚意识到，即使有了这种改变，创建一个房间仍然可能导致次优解决方案。原因是可以在创建新房间之前调整现有房间的大小。
举个例子，假设我们在四个房间开四个会议。
- m1(尺寸4)在4个房间
- m2(尺寸2)在4个房间
- m3(尺寸1)在2室
- m4(尺寸1)是在一个2室
我们试图增加m5(大小为5)。我提议的算法修改将创建一个新的5个房间，在累积容量上增加5个房间。然而，我们可以将m2的房间大小调整为5个房间，让m5去那里，并为m2创建一个大小为2的新房间。这只会使累积容量增加2。
有人可能会想，为什么不把m2放在一个2个房间(取代m3)，并创建一个新的1个房间。调整房间的大小是比较困难的，因为我们不能保证需要它的会议开始时房间会开放。增加房间更容易，因为那个房间会一直在那里;它没有被使用，因为我们刚刚在算法的这一步创建了它。
次优算法修改如上所述，这被证明是次优的，但我将保留它，直到我能想到更好的替代方案。
考虑到上面的场景，你需要在任何时候做一些额外的工作来创建一个新的房间:
- 查找当前活动的所有会议(包括您当前正在评估的会议)的列表。
- 从最大的会议开始，将每个会议分配到一个房间。
- 当您到达无法分配的会议时，您必须创建房间的大小。
因此，在上面的例子中，当需要创建一个新房间时，这个更改在第5步开始发挥作用。以上每一步的说明:
- 当前活动的所有会议:{m2, m3, m4, m5}。为记录，当前房间为{3,2,1}
- 从最大开始，将每次会议分配到一个房间{m2为3个房间，m5为2个房间，m3为1个房间}
- m4没有房间。因此，我们必须为它创造一个空间。m4是1号，所以新房间也是1号。
要找到召开所有会议所需的最小会议室数量和容量，首先需要将这些会议选择性地安排到房间(使用分数函数将房间容量的数量最小化)。该调度(类似于课程调度)是np完全的或np困难的。这意味着你的问题也是。
反过来，这意味着对于你的问题，没有已知的最优和可扩展的算法。贪婪算法(包括你的例子)不会一直是最优的(或者甚至不是接近最优的，如果你有更多的约束)-但至少他们会扩展:)为了得到更好的结果(如果需要)，看看优化算法，比如元启发式。
import java.util.*;
class Codechef
{
//Sorting by exchange
public static int[] Sort(int arr[],int n)
{
int temp=0;
for(int i=0;i<n-1;++i)
{
for(int j=i+1;j<n;++j)
{
if(arr[i]>arr[j])
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
return arr;
}
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int n=0; //n : Total number of trains arriving on the platform
n=sc.nextInt();
String UserInp;
String [] inp = new String[n]; //inp[] : Accepting the user input ....Arrival time#Departure time
int []Ar = new int[n];
int []Dp = new int[n];
for(int i=0;i<n;++i)
{
UserInp=sc.next();
inp[i]=UserInp;
}
System.out.println("Displaying the input:n");
for(int i=0;i<n;++i)
{
System.out.println("inp[i] : "+inp[i]);
}
for(int i=0;i<n;++i)
{
String temp=inp[i];
String a=temp.substring(0,2);
String b=temp.substring(3,5);
String c=temp.substring(6,8);
String d=temp.substring(9);
System.out.println("a : "+a);
System.out.println("b : "+b);
String x=a+b;
Ar[i]=Integer.parseInt(x);
System.out.println("x : "+x);
System.out.println("c : "+c);
System.out.println("d : "+d);
String y=c+d;
Dp[i]=Integer.parseInt(y);
System.out.println("y : "+y);
}
System.out.println("Displaying the arrival time : ");
for(int i=0;i<n;++i)
{
System.out.println(Ar[i]);
}
System.out.println("Displaying the departure time : ");
for(int i=0;i<n;++i)
{
System.out.println(Dp[i]);
}
Ar=Sort(Ar,n);
System.out.println("Displaying arrival time in ascending order :");
for(int i=0;i<n;++i)
{
System.out.println(Ar[i]);
}
Dp=Sort(Dp,n);
System.out.println("Displaying departure time in ascending order :");
for(int i=0;i<n;++i)
{
System.out.println(Dp[i]);
}
int count=0;
int need=0;
int i=0,j=0;
while(i<n && j<n)
{
if(Ar[i]<Dp[j])
{
++need;
if(need>count)
{
count=need;
}
++i;
}
else if(Ar[i]>Dp[j])
{
--need;
++j;
}
if(need==-1)
{
break;
}
}
if(need!=-1)
{
System.out.println("Required answer : "+count);
}
else
{
System.out.println("Invalid input");
}
}
}
Input:
6
09:00#09:10
12:00#09:40
09:50#11:20
11:00#11:30
15:00#19:00
18:00#20:00
Output:
Displaying the input:
inp[i] : 09:00#09:10
inp[i] : 12:00#09:40
inp[i] : 09:50#11:20
inp[i] : 11:00#11:30
inp[i] : 15:00#19:00
inp[i] : 18:00#20:00
a : 09
b : 00
x : 0900
c : 09
d : 10
y : 0910
a : 12
b : 00
x : 1200
c : 09
d : 40
y : 0940
a : 09
b : 50
x : 0950
c : 11
d : 20
y : 1120
a : 11
b : 00
x : 1100
c : 11
d : 30
y : 1130
a : 15
b : 00
x : 1500
c : 19
d : 00
y : 1900
a : 18
b : 00
x : 1800
c : 20
d : 00
y : 2000
Displaying the arrival time :
900
1200
950
1100
1500
1800
Displaying the departure time :
910
940
1120
1130
1900
2000
Displaying arrival time in ascending order :
900
950
1100
1200
1500
1800
Displaying departure time in ascending order :
910
940
1120
1130
1900
2000
Invalid input
The above is a detailed solution for the approach stated in the link below:
http://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/
这是我的java解决方案。
class Meeting{
LocalTime start;
LocalTime end;
Meeting(LocalTime start, LocalTime end){
this.start = start;
this.end = end;
}
}
public static int meeingRoom(List<Meeting> list){
//use queue structure to store the room in use
Queue<Meeting> rooms = new LinkedList<Meeting>();
rooms.add(list.get(0));
for(int i = 1; i< list.size(); i++){
Meeting current = list.get(i);
//max: keep the max of ever occupied
//occupied: so far occupied room
int max = 1, occupied = 1;
List<Meeting> rooms = new ArrayList<Meeting>();
rooms.add(list.get(0));
for(int i = 1; i< list.size(); i++){
Meeting current = list.get(i);
int roomSize = rooms.size();
//check all previous rooms to release finish room
for(int j = 0; j < roomSize; j++){
if(j >= rooms.size()) break;
Meeting previous = rooms.get(j);
if(current.start.compareTo(previous.end) >= 0){
rooms.remove(j);
}
rooms.add(current);
//when all the rooms once occupied, all remove
//reset the occupied
if(rooms.size() == 1 ){
max = Math.max(occupied, max);
occupied = 1;
}else{
occupied = Math.max(occupied, rooms.size());
};
}
//the last time added room hasn't been check
return Math.max(occupied, max);
}