加权间隔调度与两个可用的“工人”

9
1 2 1
1 3 3
2 4 1
3 5 1
4 6 2
5 7 1
6 8 2
7 9 1
8 10 2

“9”是间隔量,列定义为

s f v

s=start time
f=finish time
v=weight

到目前为止,我已经使用二进制搜索来确定“p”值,该值是最右边的前一个间隔并将其存储在数组中.从那里我一次一个地检查输入变量,确定最大权重以及当前间隔是否应该包含在工作人员“队列”中,因为我将调用它.

到目前为止,这是我的代码：

#include <stdio.h>
#include <stdlib.h>

#define TABSIZE (100)

int n,s[TABSIZE],f[TABSIZE],v[TABSIZE],p[TABSIZE],M[TABSIZE],M2[TABSIZE];


int binSearchLast(int *a,int n,int key)
{
// Input: int array a[] with n elements in ascending order.
//        int key to find.
// Output: Returns subscript of the last a element <= key.
//         Returns -1 if key<a[0].
// Processing: Binary search.

int low,high,mid;
low=0;
high=n-1;

// subscripts between low and high are in search range.
// size of range halves in each iteration.
// When low>high,low==high+1 and a[high]<=key and a[low]>key.
while (low<=high){
    mid=(low+high)/2;
    if (a[mid]<=key)
        low=mid+1;
    else
        high=mid-1;
}

return high;
}

main()
{
int i,j,sum=0,sum2=0;

scanf("%d",&n);
f[0]=(-999999); // For binarySearchLast
for (i=1;i<=n;i++)
    scanf("%d %d %d",&s[i],&f[i],&v[i]);
for (i=2;i<=n && f[i-1]<=f[i];i++);
    if (i<=n){
        printf("Intervals not ordered by finish time %dn",__LINE__);
        exit(0);
    }

for (i=1;i<=n;i++)
    p[i]=binSearchLast(f,n+1,s[i]);

M[0]=0;
M2[0]=0;

//checks to see if the resulting weight is bigger in a certain queue
for (i=1;i<=n;i++){
    if(v[i]+M[p[i]]>M[i-1] && !(v[i]+M2[p[i]]>M2[i-1]))
        M[i]=v[i]+M[p[i]];
    else if(v[i]+M2[p[i]]>M2[i-1] && !(v[i]+M[p[i]]>M[i-1]))
        M2[i]=v[i]+M2[p[i]];
    else
        M[i]=M[i-1];
}


printf("nnroom 1:nn");
for (i=n;i>0; ){
    if (v[i]+M[p[i]]>=M[i-1]){
        printf("%d %d %dn",s[i],f[i],v[i]);
        sum+=v[i];
        i=p[i];
    }
    else
        i--;
}
printf("nnroom 2:nn");
for (i=n;i>0; ){
    if (v[i]+M2[p[i]]>=M2[i-1]){
        printf("%d %d %dn",v[i]);
        sum2+=v[i];
        i=p[i];
    }
    else
        i--;
}

printf("sum 1 is %dn",sum);
printf("sum 2 is %dn",sum);
}

这似乎适用于1号房间,但是出于某种原因,2号房间的队列完全相同.这是我目前的输出：

room 1:

8 10 2
6 8 2
4 6 2
2 4 1
1 2 1

room 2:

8 10 2
6 8 2
4 6 2
2 4 1
1 2 1

当“正确”输出应如下所示：

room 1:

8 10 2
6 8 2
4 6 2
2 4 1
1 2 1

room 2:

7 9 1
5 7 1
3 5 1
1 3 3

任何见解都将受到高度赞赏.

编辑**
看着它我认为它实际上可能与我在确定打印结果时确定M []和M2 []中包含哪些间隔的方式有关.似乎两个房间的输出是相同的巧合.我仍然没有想出要怎么做才能纠正这个问题,但我仍在寻找建议.