2071 - Maximum Number of Tasks You Can Assign

info

• 문제 보기: 2071 - Maximum Number of Tasks You Can Assign
• 소요 시간: 58분 55초
• 풀이 언어: java
• 체감 난이도: 3️⃣~4️⃣ (3.3)
• 리뷰 횟수: ✅

풀이 키워드

스포주의

정렬 이진탐색 그리디

풀이 코드

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)$ 과 $n^2log(n)$ 의 사이 어딘가 ( $nlog(n)$ 에 훨씬 가깝긴 함)

메모

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