Can you provide example input and output ?
On Thu, May 12, 2011 at 9:32 AM, ganesha suresh.iyenga...@gmail.com wrote:
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
vectorNODEPTR 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);
vectorNODEPTR::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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
regards,
chinna.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
