Job Scheduling의 최대 이익 Leetcode 솔루션

난이도 하드
자주 묻는 질문 Airbnb 아마존 골드 피처 문틀 구글 Microsoft Swiggy 동네 짱
배열 이진 검색 동적 프로그래밍 정렬조회수 52

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

또한 Job Scheduling의 최대 이익 LeetCode 솔루션 – "작업 스케줄링의 최대 이익"은 귀하에게 주어진 n 각 작업이 시작되는 작업 시작시간[i] 과에 종료 종료시간[i] 의 이익을 얻는 것과 이익[i].

두 개의 선택된 작업이 겹치지 않도록 우리가 가질 수 있는 최대 이익을 반환해야 합니다. 또한 작업이 종료되는 경우 시간 x, 그러면 한 번에 다른 작업을 시작할 수 있습니다. x보다 크거나 같음.

예:

Job Scheduling의 최대 이익 Leetcode 솔루션

Input:  startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120

설명 :

  • 첫 번째와 네 번째 직업을 선택하면 120의 이익을 얻을 수 있으며 이것이 우리가 얻을 수 있는 최대 이익입니다.
  • 첫 번째 작업과 네 번째 작업은 겹치지 않기 때문에 동시에 수행할 수 있습니다.
Input:  startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150

설명 :

  • 첫 번째, 네 번째, 다섯 번째 직업을 선택하면 최대 이익이 150입니다.
  • 선택한 하위 집합은 겹치지 않습니다.

접근

아이디어 :

  1. 이 문제를 해결하기 위한 주요 아이디어는 동적 프로그래밍이진 검색.
  2. 우선, 우리는 종류 의 작업 감소하지 않는 차수 자신의 종료 시간 이를 통해 최대 이익을 쉽게 계산하는 데 도움이됩니다. 동적 프로그래밍.
  3. 하자 dp[i] = 첫 번째 i+1개의 작업을 고려할 때 얻을 수 있는 최대 이익.
  4. 각 인덱스에는 두 가지 경우가 있습니다.
    1. 현재 작업 선택: 현재 작업을 선택하면 이 작업은 startTime[i]에서 시작됩니다. 따라서 우리가 가질 수 있는 최대 이익은 현재 이익 + dp[j]. dp[j]는 endTime[j]가 startTime[i]보다 작거나 같도록 하는 가장 큰 인덱스 j이고 j는 i보다 엄격하게 작아야 합니다.. 유효한 j가 존재하는 경우 dp[i] = 현재 이익 + dp[j] 그렇지 않으면 dp[i] = 현재 이익.
      1. endTime[i]이 startTime[i] 및 j보다 작거나 같도록 가장 큰 인덱스 j를 계산하려면 이진 검색 작업이 이미 종료 시간의 내림차순으로 정렬되어 있으므로 적절한 인덱스를 찾으려면
    2. 현재 작업을 선택하지 마십시오. 이 경우 dp[i] = dp[i-1]입니다.
  5. 우리는 걸릴 필요가 위의 두 경우 모두 최대 각 인덱스의 값을 계산합니다.
  6. 우리의 대답은 dp[n-1]이 될 것입니다.

암호

Job Scheduling의 최대 이익 Leetcode C++ 솔루션:

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        vector<vector<int>> jobs;
        for(int i=0;i<n;i++){
            jobs.push_back({startTime[i],endTime[i],profit[i]});
        }
        sort(jobs.begin(),jobs.end(),[&](const vector<int>& a,const vector<int>& b){
           if(a[1]==b[1]){
               return a[0] < b[0];
           } 
           return a[1] < b[1];
        });
        vector<int> dp(n);
        dp[0] = jobs[0][2];
        for(int i=1;i<n;i++){
            dp[i] = dp[i-1];
            int l = 0,r = i - 1,prev = 0;
            while(l<=r){
                int mid = (l+r)/2;
                if(jobs[mid][1]<=jobs[i][0]){
                    prev = dp[mid];
                    l = mid + 1;
                }
                else{
                    r = mid - 1;
                }
            }
            dp[i] = max(dp[i],jobs[i][2]+prev);
        }
        return dp[n-1];
    }
};

Job Scheduling의 최대 이익 Leetcode Java 솔루션:

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];
        for(int i=0;i<n;i++){
            jobs[i] = new int[] {startTime[i],endTime[i],profit[i]};
        }
        Arrays.sort(jobs,(a,b)->a[1]-b[1]);
        int[] dp = new int[n];
        dp[0] = jobs[0][2];
        for(int i=1;i<n;i++){
            dp[i] = dp[i-1];
            int l = 0,r = i - 1,prev = 0;
            while(l<=r){
                int mid = (l+r)/2;
                if(jobs[mid][1]<=jobs[i][0]){
                    prev = dp[mid];
                    l = mid + 1;
                }
                else{
                    r = mid - 1;
                }
            }
            dp[i] = Math.max(dp[i],jobs[i][2]+prev);
        }
        return dp[n-1];
    }
}

Job Scheduling의 최대 이익을 위한 복잡성 분석 Leetcode 솔루션

시간 복잡성

위 코드의 시간 복잡성은 O (NlogN) 전체 입력 배열을 한 번만 탐색하고 각 인덱스에 대해 이진 검색을 적용합니다. 여기서 N = 입력 배열의 크기입니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. 의 위에). 계산된 값을 저장하기 위해 선형 배열을 사용하고 있습니다.

균열 시스템 설계 인터뷰
Translate »