title: weighted interval scheduling with two available "workers"
body: <p>I'm attempting to write a piece of code that takes in a set of weighted intervals and distribute them optimally between two "workers" maximizing the weight. An example of input would be the following.</p>
  
  <pre><code>9
  1 2 1
  1 3 3
  2 4 1
  3 5 1
  4 6 2
  5 7 1
  6 8 2
  7 9 1
  8 10 2
  </code></pre>
  
  <p>"9" is the amount of intervals and the columns are defined as </p>
  
  <pre><code>s f v
  
  s=start time
  f=finish time
  v=weight
  </code></pre>
  
  <p>So far I have used a binary search to determine the "p" value which is the rightmost preceding interval and stored it in an array.  From there I go through the input variables one at a time determining the max weight and whether or not the current interval should be included in either workers "queue" as I will call it. </p>
  
  <p>Here is my code so far:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  
  #define TABSIZE (100)
  
  int n,s[TABSIZE],f[TABSIZE],v[TABSIZE],p[TABSIZE],M[TABSIZE],M2[TABSIZE];
  
  
  int binSearchLast(int *a,int n,int key)
  {
  // Input: int array a[] with n elements in ascending order.
  //        int key to find.
  // Output: Returns subscript of the last a element &lt;= key.
  //         Returns -1 if key&lt;a[0].
  // Processing: Binary search.
  
  int low,high,mid;
  low=0;
  high=n-1;
  
  // subscripts between low and high are in search range.
  // size of range halves in each iteration.
  // When low&gt;high, low==high+1 and a[high]&lt;=key and a[low]&gt;key.
  while (low&lt;=high){
      mid=(low+high)/2;
      if (a[mid]&lt;=key)
          low=mid+1;
      else
          high=mid-1;
  }
  
  return high;
  }
  
  main()
  {
  int i,j,sum=0,sum2=0;
  
  scanf("%d",&amp;n);
  f[0]=(-999999); // For binarySearchLast
  for (i=1;i&lt;=n;i++)
      scanf("%d %d %d",&amp;s[i],&amp;f[i],&amp;v[i]);
  for (i=2;i&lt;=n &amp;&amp; f[i-1]&lt;=f[i];i++);
      if (i&lt;=n){
          printf("Intervals not ordered by finish time %d\n",__LINE__);
          exit(0);
      }
  
  for (i=1;i&lt;=n;i++)
      p[i]=binSearchLast(f,n+1,s[i]);
  
  M[0]=0;
  M2[0]=0;
  
  //checks to see if the resulting weight is bigger in a certain queue
  for (i=1;i&lt;=n;i++){
      if(v[i]+M[p[i]]&gt;M[i-1] &amp;&amp; !(v[i]+M2[p[i]]&gt;M2[i-1]))
          M[i]=v[i]+M[p[i]];
      else if(v[i]+M2[p[i]]&gt;M2[i-1] &amp;&amp; !(v[i]+M[p[i]]&gt;M[i-1]))
          M2[i]=v[i]+M2[p[i]];
      else
          M[i]=M[i-1];
  }
  
  
  printf("\n\nroom 1:\n\n");
  for (i=n;i&gt;0; ){
      if (v[i]+M[p[i]]&gt;=M[i-1]){
          printf("%d %d %d\n",s[i],f[i],v[i]);
          sum+=v[i];
          i=p[i];
      }
      else
          i--;
  }
  printf("\n\nroom 2:\n\n");
  for (i=n;i&gt;0; ){
      if (v[i]+M2[p[i]]&gt;=M2[i-1]){
          printf("%d %d %d\n",s[i],f[i],v[i]);
          sum2+=v[i];
          i=p[i];
      }
      else
          i--;
  }
  
  printf("sum 1 is %d\n",sum);
  printf("sum 2 is %d\n",sum);
  }
  </code></pre>
  
  <p>This seems to work for room 1, but room 2 comes out with the exact same queue for some reason.  This is my current output:</p>
  
  <pre><code>room 1:
  
  8 10 2
  6 8 2
  4 6 2
  2 4 1
  1 2 1
  
  room 2:
  
  8 10 2
  6 8 2
  4 6 2
  2 4 1
  1 2 1
  </code></pre>
  
  <p>when the "correct" output should look like:</p>
  
  <pre><code>room 1:
  
  8 10 2
  6 8 2
  4 6 2
  2 4 1
  1 2 1
  
  room 2:
  
  7 9 1
  5 7 1
  3 5 1
  1 3 3
  </code></pre>
  
  <p>Any insight would be highly appreciated.</p>
  
  <p>EDIT**
  Looking at it I'm thinking it might actually have to do with the way I am determining which intervals are included in M[] and M2[] when I print out the result.  It seems it is just a coincidence the output for the two rooms is the same. I still haven't figured out what to do to correct that however, I'm still looking for advice.</p>