Can some one help in finding out the bug in the below code.
Input: (left,right,weight) representing intervals
Output: maximum weight of non-overlapping intervals
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
struct point
{
int value;
bool isLeft;
long int weight;
int index;
struct point* prev;
};
typedef struct point* NODEPTR;
bool compare (NODEPTR A,NODEPTR B)
{
return (A->value < B->value);
}
int main()
{
int numIntervals;
cin >> numIntervals;
// read the intervals and sort the list
vector<NODEPTR> points;
for (int i=0; i < numIntervals; i++)
{
NODEPTR p1 = new point;
p1->isLeft = true;
p1->weight = 0;
p1->prev = NULL;
cin >> p1->value;
points.push_back(p1);
NODEPTR p2 = new point;
p2->isLeft = false;
p2->prev = p1;
cin >> p2->value;
cin >> p2->weight;
points.push_back(p2);
}
sort(points.begin(),points.end(),compare);
vector<NODEPTR>::iterator it;
int idx=1;
for (it=points.begin(); it!=points.end(); ++it)
{
(*it)->index = idx++;
}
/*for (it=points.begin(); it!=points.end(); ++it)
{
if ((*it)->prev != NULL)
cout << (*it)->prev->value << " " << (*it)->value << "
" << (*it)-
>weight << " " << (*it)->prev->index << endl;
}*/
int score[2*numIntervals + 1];
for (int i=0; i <= 2*numIntervals; i++)
{
score[i] = 0;
}
int i = 1;
for (it=points.begin(); it!=points.end(); ++it)
{
// right end of the interval
if (false == (*it)->isLeft)
{
int j = (*it)->prev->index;
int t1 = score[j] + (*it)->weight;
int t2 = score[i-1];
if (t1 < t2)
score[i] = t2;
else
score[i] = t1;
}
else
{
score[i] = score[i-1];
}
i++;
}
cout << "Max weight is " << score[2*numIntervals] << " " <<
2*numIntervals << endl;
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
