[LeetCode] 1235. Maximum Profit in Job Scheduling

https://leetcode.com/problems/maximum-profit-in-job-scheduling/description/

Maximum Profit in Job Scheduling - LeetCode

leetcode - Maximum Profit in Job Scheduling

문제 유형 : 다이나믹 프로그래밍, 정렬, 이진탐색, 재귀

문제 난이도 : Hard

 

문제

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.

 

우리는 n 개의 일이 있다. i번째 일은 startTime[i]에서 시작해서 endTime[i]에서 끝나고, profit[i]만큼의 수익을 본다.

배열 startTime, endTime, profit을 받는다.

같은 시간에 겹치지 않고 일을 했을 때, 얻을 수 있는 수익의 최대값을 구하시오.

x시간에 끝나면, x시간에 다른 일을 시작할 수 있다.

 

풀이

처음에는 2차원 루프를 돌면서 이전 작업들에서 연달아 일을 할 수 있으면 이번 일을 하는 것으로 타뷸레이션dp를 했는데,

작업 시작 시간이 순서에 무관하게 되어있어서 실패했다.

정렬을 해주고 돌리니, 시간초과가 났다.

 

그래서 다른 사람의 풀이의 도움을 보았다.

우선 2차원 배열에 {startTime, endTime, profit}의 형태로 담고 정렬한 것까지는 똑같았고,

이 풀이에서는 이진 탐색을 이용해서 현재 일이 끝나고 다음 할 수 있는 일을 따로 배열에 저장시켰다.

 

그 뒤, 재귀 탑다운dp를 이용해서 기저상황 처리(인덱스 == n인 경우 또는 dp[i]에 값이 있는 경우)를 했고,

이번 인덱스의 값을 넣느냐, 넣지 않느냐에 따라 처리를 다르게 하였다.

• 이번 인덱스에서 값을 넣는 경우 : jobs[i][2] + dfs(next[i])의 값(현재 profit + 현재 일 이후 다음 인덱스 재귀연산)
• 이번 인덱스에서 값을 넣지 않는 경우 : dfs(i+1)의 값(이번 일은 건너뛰는 경우의 처리)

그 뒤, dp[i]에 인덱스 값을 넣었을 때와 넣지 않았을 때 중에서 더 큰 값을 저장하고 반환

 

 

코드

C++

static const int __ = []() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int n;
    vector<int> dp;
    vector<vector<int>> jobs; // {startTime, endTime, profit}
    vector<int> next;

	// 이진탐색으로 다음 인덱스 계산
    void binary_search() {
        for(int i = 0; i < n; i++) {
            next[i] = upper_bound(jobs.begin()+i, jobs.end(), vector<int>{jobs[i][1], 0, 0}) - jobs.begin();
        }
    }

	// dfs
    int dfs(int i) {
        if(i == n) return 0;
        if(dp[i] != -1) return dp[i];

        int profit_with_i = jobs[i][2] + dfs(next[i]);
        int profit_without_i = dfs(i+1);

        return dp[i] = max(profit_with_i, profit_without_i);
    }

	// 메인
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        n = startTime.size();
        jobs.assign(n, {0, 0, 0});
        for(int i = 0; i < n; i++) {
            jobs[i] = {startTime[i], endTime[i], profit[i]};
        }

        sort(jobs.begin(), jobs.end());
        next.assign(n, -1);

        dp.assign(n+1, -1);
        binary_search();
        return dfs(0);
    }
};