[2365] Task Scheduler II

我又奢華的貼solution 了(遮臉)

用 質數來當hash的index , 如果有重覆的, 用linkedlist 往後加.

每次會記錄該val 下一次可以使用的index 

關鍵點應該是return的天數(ret) 會在休息時往上加，這時可能會超過array一開始的index i

所以許多地方都要用到max 看是要拿天數還是拿index 來做。

https://leetcode.com/problems/task-scheduler-ii/solutions/7280026/c-hash-table-with-linked-list-by-qmonste-57fa

struct node{

int val;

long long idx;

struct node* next;

};

#define max(A,B) (A>B)?(A):(B)

long long taskSchedulerII(int* tasks, int tasksSize, int space) {

int hash_size = 100*tasksSize;

struct node** hash = calloc (hash_size, sizeof(struct node*));

long long ret = 0;

for (int i=0;i<tasksSize; i++)

{

int idx = tasks[i]%97;

struct node* ptr = hash[idx];

struct node* pre = NULL;

while (ptr != NULL)

{

if (ptr->val ==tasks[i])

break;

pre = ptr;

ptr = ptr->next;

}

if (ptr==NULL)

{

ptr = calloc (1,sizeof(struct node));

if (pre != NULL)

pre->next = ptr;

else

hash[idx] = ptr;

ptr->val = tasks[i];

ptr->idx = max(ret+space+1,i+space+1);

ptr->next = NULL;

}

else

{

if (ptr->val== tasks[i]) //可縮減到上面的else 其實

{

if (ptr->idx>ret)

ret+= ptr->idx-ret;

ptr->idx = max(ret+space+1,i+space+1);

}

}

ret++;

}

free(hash);

return ret;

}