kartikkukreja

Weighted Interval Scheduling

Aug 25th, 2013
191
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.15 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <stack>
  4. using namespace std;
  5.  
  6. class WeightedInterval {
  7. public:
  8.     int start, finish, weight;
  9.  
  10.     bool operator < (const WeightedInterval& x) const   {
  11.         if (finish != x.finish)
  12.             return finish < x.finish;
  13.         return start < x.start;
  14.     }
  15. } *intervals;
  16.  
  17. // returns index of the interval having greatest finish time <= val in range [lo, hi]
  18. int binary_search(int lo, int hi, int val)   {
  19.     int mid;
  20.     while (lo < hi) {
  21.         mid = lo + (hi - lo + 1) / 2;
  22.         if (intervals[mid].finish <= val)
  23.             lo = mid;
  24.         else
  25.             hi = mid - 1;
  26.     }
  27.     if (intervals[lo].finish > val)
  28.         return 0;
  29.     return lo;
  30. }
  31.  
  32. // returns index of the interval having greatest finish time <= start time of interval i
  33. int greatestNonOverlappingInterval(int i)   {
  34.     return binary_search(0, i-1, intervals[i].start);
  35. }
  36.  
  37. int main()  {
  38.     int N, i, *dp, *p;
  39.  
  40.     scanf("%d", &N); //Number of intervals
  41.     intervals = new WeightedInterval[N + 1];
  42.     for (i = 1; i <= N; i++)
  43.         scanf("%d %d %d", &intervals[i].start, &intervals[i].finish, &intervals[i].weight);
  44.  
  45.     // dummy interval used as a sentinel
  46.     intervals[0].start = intervals[0].finish = intervals[0].weight = 0;
  47.  
  48.     // sort intervals in non-decreasing order of finish times
  49.     sort(intervals + 1, intervals + N + 1);
  50.  
  51.     dp = new int[N + 1];
  52.     p = new int[N + 1];
  53.     dp[0] = p[0] = 0;
  54.  
  55.     // construct the value of the optimal solution
  56.     for (i = 1; i <= N; i++)    {
  57.         p[i] = greatestNonOverlappingInterval(i);
  58.         dp[i] = max(intervals[i].weight + dp[p[i]], dp[i-1]);
  59.     }
  60.  
  61.     // construct the optimal solution
  62.     stack <int> opt;
  63.     for (i = N; i > 0; )    {
  64.         if (intervals[i].weight + dp[p[i]] >= dp[i-1])  {
  65.             opt.push(i);
  66.             i = p[i];
  67.         } else
  68.             i--;
  69.     }
  70.  
  71.     // optimal solution
  72.     printf("%d\n", dp[N]);
  73.     while (!opt.empty())    {
  74.         i = opt.top();
  75.         opt.pop();
  76.         printf("%d %d %d\n", intervals[i].start, intervals[i].finish, intervals[i].weight);
  77.     }
  78.  
  79.     return 0;
  80. }
Add Comment
Please, Sign In to add comment