diff options
Diffstat (limited to 'course_schedule.c')
-rw-r--r-- | course_schedule.c | 69 |
1 files changed, 69 insertions, 0 deletions
diff --git a/course_schedule.c b/course_schedule.c new file mode 100644 index 0000000..81a64a9 --- /dev/null +++ b/course_schedule.c @@ -0,0 +1,69 @@ +// 207. Course Schedule +#include <stdbool.h> +#include <stdlib.h> + +/* + * there are a total of 'num_courses' courses you have to take labeled from 0 to + * 'num_courses - 1'. you are given an array 'prerequisites' where + * 'prerequisites[i] = [ai, bi]' indicates that you must take course 'bi' first + * if you want to take course 'ai'. return true if you can finish all courses, + * otherwise, return false + */ + +int cmp(const void *a, const void *b) { + int *arr1 = *(int **)a; + int *arr2 = *(int **)b; + return arr1[1] - arr2[1]; +} + +int bts(int **arr, int arr_size, int val) { + int left = 0, right = arr_size - 1, mid; + while (left < right) { + mid = left + (right - left) / 2; + if (arr[mid][1] >= val) + right = mid; + else + left = mid + 1; + } + if (arr[left][1] == val) + return left; + else + return -1; +} + +bool canFinish(int num_courses, int **prerequisites, int prerequisites_size, + int *prerequisites_col_size) { + int *pre_cnt = calloc(num_courses, sizeof(int)); + for (int i = 0; i < prerequisites_size; i++) + pre_cnt[prerequisites[i][0]]++; + int *queue = malloc(1000 * sizeof(int)), queue_idx = 0; + for (int i = 0; i < num_courses; i++) + if (!pre_cnt[i]) { + queue[queue_idx] = i; + queue_idx++; + } + if (prerequisites_size) + qsort(prerequisites, prerequisites_size, sizeof(int *), cmp); + int course_seq = 0; + while (queue_idx) { + queue_idx--; + int val = queue[queue_idx]; + course_seq++; + if (prerequisites_size) { + int k = bts(prerequisites, prerequisites_size, val); + if (k != -1) + while (k < prerequisites_size && prerequisites[k][1] == val) { + pre_cnt[prerequisites[k][0]]--; + if (!pre_cnt[prerequisites[k][0]]) { + queue[queue_idx] = prerequisites[k][0]; + queue_idx++; + } + k++; + } + } + } + if (course_seq != num_courses) + return false; + else + return true; +} |