fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Job sequencing
  4. //
  5. //  Created by Himanshu on 14/08/21.
  6.  
  7. #include <iostream>
  8. #include <algorithm>
  9. #include <vector>
  10.  
  11. using namespace std;
  12.  
  13. const int N = 5;
  14.  
  15. struct node {
  16.     int p,d;
  17. };
  18.  
  19. bool cmp (const struct node &a, const struct node &b) {
  20.     return a.p> b.p;
  21. }
  22.  
  23. void solve (int p[], int d[]) {
  24.     struct node q[N];
  25.     int slot[N] = {0};
  26.     int ans = 0;
  27.     vector<int> sol;
  28.     for (int i=0; i<N; i++) {
  29.         q[i].p = p[i];
  30.         q[i].d = d[i];
  31.     }
  32.     sort(q, q+N, &cmp);
  33.  
  34.     for (int i=0; i<N; i++) {
  35.         if (slot[q[i].d-1] == 0) {
  36.             ans += q[i].p;
  37.             sol.push_back(i);
  38.             slot[q[i].d-1] = 1;
  39.         } else {
  40.             int j = q[i].d -1;
  41.             while (j>=0 && slot[j] != 0) {
  42.                 j--;
  43.             }
  44.             if (j >= 0) {
  45.                 ans += q[i].p;
  46.                 sol.push_back(i);
  47.                 slot[j] = 1;
  48.             }
  49.         }
  50.     }
  51.     cout<<"Job selected\n";
  52.     for (int i=0; i<sol.size(); i++) {
  53.         cout<<q[sol[i]].p<<" ";
  54.     }
  55.     cout<<"\nProfit: "<<ans<<"\n";
  56. }
  57.  
  58. int main() {
  59.     int p[] = {10, 5, 20, 15, 1};
  60.     int d[] = {1, 3, 2, 2, 3};
  61.     solve(p, d);
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0s 5552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Job selected
20 15 5 
Profit: 40
https://ideone.com/uxigXM
language:
C++ 4.3.2 (gcc-4.3.2)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!