[algogeeks] exon chaining

[ganesha]

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 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.