621. 任务调度器/875. 爱吃香蕉的珂珂

621. 任务调度器

• 相关标签： 贪心 数组 队列

/*
A - Z  task  - char[26] 
n A1 .. A2  A2-A1 = N 
时间最短 -- 》 待命的时间最短 

对于频率最高的 k   耗时 k * n
A1,,,,,,A2,,,,,A3 ,,,,,,Ak-1.....|Ak
    (n)
    (n+1)
(k-1)(n+1) +#(num == K)
(3 -1) (2 + 1) + 2 = 8
except n = 0
except (k-1)(n+1) +#(num == K) < tasksSize --> no need idle --> tasksSize

感觉是个数学题。。。

*/
#define BUFLEN 26
#define KEY(x) (x - 'A')
int leastInterval(char* tasks, int tasksSize, int n){
    if (n == 0) {
        return tasksSize;
    }

    int hm[BUFLEN] = {0};
    for (int i = 0; i < tasksSize; i++) {
        hm[KEY(tasks[i])]++;
    }
    int maxfreq = -1;
    
    for (int i =0; i < BUFLEN; i++) {
        maxfreq = (hm[i] > maxfreq) ? hm[i] : maxfreq;
    }

    int maxfreqnum = 0;
    for (int i = 0; i < BUFLEN; i++) {
        if (hm[i] == maxfreq) {
            maxfreqnum++;
        }
    }

    printf("%d-%d\n", maxfreq, maxfreqnum);
    int res = (maxfreq - 1) * (n + 1) + maxfreqnum;
    return (res < tasksSize)? tasksSize : res;
}

875. 爱吃香蕉的珂珂

• 相关标签： 二分查找

/*
H hours eat N piles

k 速度能吃掉 那么 K+1 肯定能吃掉 

用二分搜索 

*/


int canEat(int* piles, int pilesSize, int H, int K)
{
    int h = 0;
    for (int i = 0; i < pilesSize; i++) {
        h += ((piles[i] % K) == 0 ?( piles[i] / K) : (piles[i] / K + 1));
    }
    return h <= H;
}

int minEatingSpeed(int* piles, int pilesSize, int H){

    int maxV = 0;
    long long sum = 0; // 可能会越界
    for (int i = 0; i < pilesSize; i++) {
        maxV = (piles[i] > maxV) ? piles[i] : maxV;
        sum += piles[i];
    }
    int minV = (sum / H); // 有可能是0 
    int mid;
    int left = (minV == 0)? 1: minV;
    int right = maxV;
    printf("%d-%d\n", left, right);
    while (left <= right) {
        mid = (left + right)/2;
        if (canEat(piles, pilesSize, H,mid)) {
            right = mid -1;
        } else {
            left = mid + 1;
        }
    }

    return (canEat(piles, pilesSize, H,left)) ? left : right;
}