Skip to main content

2071 - Maximum Number of Tasks You Can Assign

info

풀이 키워드​

스포주의

정렬 이진탐색 그리디


풀이 코드​

info
  • 메모리: 55760 KB
  • 시간: 64 ms
class Solution {
    int[] tasks;
    int[] workers;
    int pills;
    int strength;

    // check k tasks assignment availability
    public boolean avail(int k) {
        int tdx = 0; // task index
        int pCnt = pills; // number of pills
        Deque<Integer> q = new ArrayDeque<>(); // task queue

        // workers: low(start w/ best attempt) -> high | tasks: lowest -> high
        for (int wdx = workers.length-k; wdx < workers.length; ++wdx) {
            // q: all cadidate tasks that wdx can handle including pill strength
            while (tdx < k && tasks[tdx] <= workers[wdx]+strength) {
                q.add(tasks[tdx++]);
            }

            if (q.isEmpty()) return false;
            
            if (q.peekFirst() <= workers[wdx]) q.pollFirst();
            else if (pCnt == 0) return false; // need pill but none left
            else {
                --pCnt;
                q.pollLast(); // use pill & task hardest
            }
        }

        return true;
    }

    public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
        this.pills = pills;
        this.strength = strength;

        // sort for bsearch
        Arrays.sort(tasks);
        Arrays.sort(workers);
        this.tasks = tasks;
        this.workers = workers;

        // bsearch
        int l = 0;
        int r = Math.min(tasks.length, workers.length);
        while (l < r) {
            int m = (l+r+1) / 2;
            if (avail(m)) l = m;
            else r = m - 1;
        }

        return l;
    }
}

풀이 해설​

WIP

시간복잡도는 nlog(n)nlog(n) 과 n2log(n)n^2log(n) 의 사이 어딘가 ( nlog(n)nlog(n) 에 훨씬 가깝긴 함)


메모​

  • 유형은 다 유추됐는데 스팀팩 꽂고 난 후의 로직이 좀 까다로웠다.
  • 5월 첫날 노동절 문제라서 댓글창이 재밌음 ㅋㅋ