Advertisement
Guest User

Untitled

a guest
Jun 15th, 2019
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.05 KB | None | 0 0
  1. public:
  2. int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
  3. int w = workers.size();
  4. int b = bikes.size();
  5. vector<vector<int> > dist;
  6.  
  7. //complexity O(w*b)
  8. for( vector<int> worker : workers ) {
  9. vector<int> v;
  10. for( vector<int> bike : bikes ) {
  11. v.push_back( abs(worker[0]-bike[0]) + abs(worker[1]-bike[1]) );
  12. }
  13. dist.push_back(v);
  14. }
  15.  
  16. vector<int> vis(b,0);
  17. //complexity O(b^w) My calculation
  18. return bikeAssign(dist, vis, 0, w );
  19. }
  20.  
  21.  
  22. // COMPLEXITY OF THIS FUNCTION ????
  23.  
  24. int bikeAssign( vector<vector<int> > &dist, vector<int> &vis, int cnt, int w ) {
  25. if( cnt == w )
  26. return 0;
  27.  
  28. int res = INT_MAX;
  29. for( int i=0;i<dist[0].size();i++ ) {
  30. if( vis[i] == 0 ) {
  31. vis[i] = 1;
  32. res = min( res, dist[cnt][i] + bikeAssign( dist, vis, cnt+1, w) );
  33. vis[i] = 0;
  34. }
  35. }
  36.  
  37. return res;
  38. }
  39. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement