Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public:
- int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
- int w = workers.size();
- int b = bikes.size();
- vector<vector<int> > dist;
- //complexity O(w*b)
- for( vector<int> worker : workers ) {
- vector<int> v;
- for( vector<int> bike : bikes ) {
- v.push_back( abs(worker[0]-bike[0]) + abs(worker[1]-bike[1]) );
- }
- dist.push_back(v);
- }
- vector<int> vis(b,0);
- //complexity O(b^w) My calculation
- return bikeAssign(dist, vis, 0, w );
- }
- // COMPLEXITY OF THIS FUNCTION ????
- int bikeAssign( vector<vector<int> > &dist, vector<int> &vis, int cnt, int w ) {
- if( cnt == w )
- return 0;
- int res = INT_MAX;
- for( int i=0;i<dist[0].size();i++ ) {
- if( vis[i] == 0 ) {
- vis[i] = 1;
- res = min( res, dist[cnt][i] + bikeAssign( dist, vis, cnt+1, w) );
- vis[i] = 0;
- }
- }
- return res;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement