Can you provide example input and output ?
On Thu, May 12, 2011 at 9:32 AM, ganesha <[email protected]> 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
> 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.
>
>
--
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 [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.
