99클럽 코테스터디 29일차 TIL LeetCode - Maximum Profit in Job Scheduling

Maximum Profit in Job Scheduling

LeetCode Hard BinarySearch, DP, Sort

 

문제 링크

문제 설명

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i],
obtaining a profit of profit[i].

You're given the startTime, endTime and profit arrays, return the maximum profit 
you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job 
that starts at time X.

 

작업의 시작시간과, 끝나는 시간과 각각의 이득이 주어질 때, 최대로 얻을 수 있는 이득의 합을 구하면 되는 문제였다.

 

문제 풀이

 

문제를 어떻게 풀어야 할지 감이 아예 안왔다. 아직도 DP 가 섞이면 감을 못잡는 것 같다.

 

계속 고민하는 것은 의미 없을 것 같아 discuss 를 참고해 풀이했다.

 

시간을 기준으로 오름차순으로 정렬해주고, 역순으로 dp 배열을 채워주며 답을 구하는 방식이었다.

 

코드

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {

        int n=startTime.size();

        vector<pair<int,pair<int,int>>>vp;
        for(int i=0;i<n;i++){
            vp.push_back(make_pair(startTime[i],make_pair(endTime[i],profit[i])));
        }

        sort(vp.begin(),vp.end());

        for(int i=0;i<n;i++){
            startTime[i]=vp[i].first;
            endTime[i]=vp[i].second.first;
            profit[i]=vp[i].second.second;
        }

        vector<int>dp(n+1,0);

        for(int idx=n-1;idx>=0;idx--){
            int nextJobIdx = lower_bound(startTime.begin() + idx, startTime.end(), endTime[idx]) - startTime.begin();
            int inc = profit[idx] + dp[nextJobIdx];
            int exc = dp[idx+1];
            dp[idx] = max(inc, exc);
        }
        return dp[0];
    }
};

 

회고

 

리트코드에서 문제를 풀게되면 못푸는 일의 빈도가 높은 것 같은데,

백준이나 프로그래머스 보다는 리트코드에서 풀어보려고 시도해봐야겠다.