DP and sort C++ 69ms beats 99%


  • 0
    B

    Since for each city it need to search N flights, so for each week it will be NN
    a little improvement is to sort next week's information, which is N
    logN and then to search the max value. However in worst case, it will still cost N*N

    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
        int cities=days.size(),weeks=cities==0?0:days[0].size();
        if(cities==0 || weeks==0)return 0;
        for(int i=weeks-2;i>=0;i--)
        {
            vector<pair<int,int>> rank;
            for(int j=0;j<cities;j++)rank.push_back({days[j][i+1],j});
            sort(rank.begin(),rank.end(),[](pair<int,int> x,pair<int,int> y){return x.first>y.first;});
            for(int j=0;j<cities;j++)
            {
                int k=0;
                while(k<cities && (!flights[j][rank[k].second] && rank[k].second!=j ))k++;
                if(k<cities)
                days[j][i]+=rank[k].first;
                
            }
        }
       
        int result=days[0][0];
        for(int i=1;i<cities;i++)if(flights[0][i])result=max(result,days[i][0]);
        return result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.