aboutsummaryrefslogtreecommitdiff
path: root/course_schedule.c
blob: 81a64a97bb6e4c6741861b673865c55cd57d7984 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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;
}