CONVERT GIVEN C PROGRAM TO C PROGRAM include include include

CONVERT GIVEN C++ PROGRAM TO C PROGRAM

#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;

class WeightedInterval {
public:
int start, finish, weight;

bool operator < (const WeightedInterval& x) const {
if (finish != x.finish)
return finish < x.finish;
return start < x.start;
}
} *intervals;

// returns index of the interval having greatest finish time <= val in range [lo, hi]
int binary_search(int lo, int hi, int val) {
int mid;
while (lo < hi) {
mid = lo + (hi - lo + 1) / 2;
if (intervals[mid].finish <= val)
lo = mid;
else
hi = mid - 1;
}
if (intervals[lo].finish > val)
return 0;
return lo;
}

// returns index of the interval having greatest finish time <= start time of interval i
int greatestNonOverlappingInterval(int i) {
return binary_search(0, i-1, intervals[i].start);
}

int main() {
int N, i, *dp, *p;
printf(\"Enter number of intervals: \");
scanf(\"%d\", &N); //Number of intervals
intervals = new WeightedInterval[N + 1];
printf(\"Enter intervals: \ \");
for (i = 1; i <= N; i++)
scanf(\"%d %d %d\", &intervals[i].start, &intervals[i].finish, &intervals[i].weight);

// dummy interval used as a sentinel
intervals[0].start = intervals[0].finish = intervals[0].weight = 0;

// sort intervals in non-decreasing order of finish times
sort(intervals + 1, intervals + N + 1);

dp = new int[N + 1];
p = new int[N + 1];
dp[0] = p[0] = 0;

// construct the value of the optimal solution
for (i = 1; i <= N; i++) {
p[i] = greatestNonOverlappingInterval(i);
dp[i] = max(intervals[i].weight + dp[p[i]], dp[i-1]);
}

// construct the optimal solution
stack <int> opt;
for (i = N; i > 0; ) {
if (intervals[i].weight + dp[p[i]] >= dp[i-1]) {
opt.push(i);
i = p[i];
} else
i--;
}

// optimal solution
printf(\"%d\ \", dp[N]);
while (!opt.empty()) {
i = opt.top();
opt.pop();
printf(\"%d %d %d\ \", intervals[i].start, intervals[i].finish, intervals[i].weight);
}

return 0;
}

Solution

This is the code after converting into C code. Compile, run the program.

You have to debug the code in runtime to get your expected output. Do your own modification whenever required.

/**********************************/

#include <stdio.h>
#include <stdlib.h>
/*
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
*/
struct WeightedInterval {
//public:
   int start, finish, weight;
/*
   bool operator < (const WeightedInterval& x) const {
   if (finish != x.finish)
   return finish < x.finish;
   return start < x.start;
   }
   */
} *intervals;

// returns index of the interval having greatest finish time <= val in range [lo, hi]
int binary_search(int lo, int hi, int val) {
   int mid;
   while (lo < hi) {
       mid = lo + (hi - lo + 1) / 2;
       if (intervals[mid].finish <= val)
       lo = mid;
       else
       hi = mid - 1;
   }
   if (intervals[lo].finish > val)
   return 0;

return lo;
}

// returns index of the interval having greatest finish time <= start time of interval i
int greatestNonOverlappingInterval(int i) {
   return binary_search(0, i-1, intervals[i].start);
}

void sort(struct WeightedInterval* val,int size)   //additional code for sorting
{
   int i,j;
   for( i=0;i<size;i++)
   {
       for(j=i+1;j<size;j++)
       {
           if(val[i].finish>val[j].finish)
           {
               int tmp=val[i].finish;
               val[i].finish=val[j].finish;
               val[j].finish=tmp;
           }
       }
   }
}
int max(int x,int y) //additional code for max
{
   if(x>y)
       return x;
   else
       return y;
}
int main() {
   int N, i, *dp, *p;
   printf(\"Enter number of intervals: \");
   scanf(\"%d\", &N); //Number of intervals
   intervals = (struct WeightedInterval*)malloc(sizeof(struct WeightedInterval)*(N+1));//new WeightedInterval[N + 1];
   printf(\"Enter intervals: \ \");
   for (i = 1; i <= N; i++)
   scanf(\"%d %d %d\", &intervals[i].start, &intervals[i].finish, &intervals[i].weight);

   // dummy interval used as a sentinel
   intervals[0].start = intervals[0].finish = intervals[0].weight = 0;

   // sort intervals in non-decreasing order of finish times
   sort(intervals + 1, N + 1);

   dp = (int*)malloc(sizeof(int)*(N+1));//new int[N + 1];
   p = (int*)malloc(sizeof(int)*(N+1));//new int[N + 1];
   dp[0] = p[0] = 0;

   // construct the value of the optimal solution
   for (i = 1; i <= N; i++) {
   p[i] = greatestNonOverlappingInterval(i);
   dp[i] = max(intervals[i].weight + dp[p[i]], dp[i-1]);
   }

   // construct the optimal solution
   //stack <int> opt;
   int opt[N];
   for (i = N; i > 0; ) {
       if (intervals[i].weight + dp[p[i]] >= dp[i-1]) {
           opt[N-i]=N;//       opt.push(i);
       i = p[i];
       } else
       i--;
   }

   // optimal solution
   printf(\"%d\ \", dp[N]);
   int j;
   for( j=N-1;j>=0;j--)
   {
       i=opt[j];
       printf(\"%d %d %d\ \", intervals[i].start, intervals[i].finish, intervals[i].weight);
   }
   /*
   while (!opt.empty()) {
   i = opt.top();
   opt.pop();
   printf(\"%d %d %d\ \", intervals[i].start, intervals[i].finish, intervals[i].weight);
   }
   */

return 0;
}