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

오늘의 학습 키워드

---

이분탐색

문제

---

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

• 플랫폼: LeetCode
• 문제명: Maximum Profit in Job Scheduling
• 난이도: Hard

풀이

---

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        Job[] jobs = new Job[n];
        for(int i=0; i<n; i++) {
            jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
        }

        Arrays.sort(jobs);

        int[] mem = new int[n];
        mem[0] = jobs[0].p;

        for(int i=1; i<n; i++) {
            int curProfit = jobs[i].p;
            int preIdx = findLastNonOverlappingJob(jobs, i);
            // 겹치지 않는 Job이 존재하는 경우
            if(preIdx != -1) {
                curProfit += mem[preIdx];
            }
            mem[i] = Math.max(mem[i-1], curProfit);
        }

        return mem[n-1];
    }

    private int findLastNonOverlappingJob(Job[] jobs, int curIdx) {
        int left = 0;
        int right = curIdx - 1;

        while(left<=right) {
            int mid = left + (right-left)/2;
            // 다음 인덱스도 겹치지 않는 경우 -> 겹치지 않는 최대 인덱스를 찾아야 함
            if(jobs[curIdx].s >= jobs[mid + 1].e) {
                left = mid + 1;
            } 
            // 겹치지 않는 마지막 인덱스인 경우
            else if(jobs[curIdx].s >= jobs[mid].e) {
                return mid;
            }
            else {
                right = mid - 1;
            }
        }

        return -1;
    }

    static class Job implements Comparable<Job> {
        int s;
        int e;
        int p;

        public Job(int s, int e, int p) {
            this.s = s;
            this.e = e;
            this.p = p;
        }

        @Override
        public int compareTo(Job j) {
            return this.e - j.e;
        }
    }
}

접근

• 작업 종료 시간을 기준으로 오름차순 정렬하여 앞에서부터 작업들을 수행해나갑니다.

  static class Job implements Comparable<Job> {
      int s;
      int e;
      int p;
  
      public Job(int s, int e, int p) {
          this.s = s;
          this.e = e;
          this.p = p;
      }
  
      @Override
      public int compareTo(Job j) {
          return this.e - j.e;
      }
  }

  • Job 클래스를 정의하고, Comparable 인터페이스를 구현하여 정렬 조건을 지정했습니다.
• 수행하는 도중 작업 간 겹치는 부분이 발생하면 profit을 비교하여 더 큰 작업을 취합니다.

  for(int i=1; i<n; i++) {
      int curProfit = jobs[i].p;
      int preIdx = findLastNonOverlappingJob(jobs, i);
      // 겹치지 않는 Job이 존재하는 경우
      if(preIdx != -1) {
          curProfit += mem[preIdx];
      }
      mem[i] = Math.max(mem[i-1], curProfit);
  }

  • mem 배열은 Job과 동일한 사이즈의 배열로, 해당 Job까지 수행했을 때 최대 profit을 저장합니다.
  • 겹치는 부분 존재 여부는 이분탐색을 활용합니다. (물론 이분탐색을 활용하지 않고, 현재 인덱스 - 1부터 거꾸로 순회하며 최초로 겹치지 않는 인덱스를 찾아 리턴해도 됩니다.)

    private int findLastNonOverlappingJob(Job[] jobs, int curIdx) {
        int left = 0;
        int right = curIdx - 1;
    
        while(left<=right) {
            int mid = left + (right-left)/2;
            // 다음 인덱스도 겹치지 않는 경우 -> 겹치지 않는 최대 인덱스를 찾아야 함
            if(jobs[curIdx].s >= jobs[mid + 1].e) {
                left = mid + 1;
            } 
            // 겹치지 않는 마지막 인덱스인 경우
            else if(jobs[curIdx].s >= jobs[mid].e) {
                return mid;
            }
            else {
                right = mid - 1;
            }
        }
    
        return -1;
    }

  • 겹치지 않는 최초 인덱스가 존재하는 경우 → 해당 위치까지는 현재 Job과 무방한 영역이므로 현재 Job의 profit에 더하여 값을 비교합니다.

    // 겹치지 않는 Job이 존재하는 경우
    if(preIdx != -1) {
        curProfit += mem[preIdx];
    }
    mem[i] = Math.max(mem[i-1], curProfit);

소요 시간

2시간