C Solution - Binary Search & Intervals
```c []
typedef struct
{
  double percentage;
  int leftBorder;
  int rightBorder;
} Interval;

typedef struct
{
  Interval *intervals;
  int intervalsSize;
} Solution;

int cmp(const void *a, const void *b)
{
  return *(int *)a - *(int *)b;
}

int getRandom(Interval *interval)
{
  return ((rand() % (interval->rightBorder - interval->leftBorder + 1)) + interval->leftBorder);
}

int findIndex(Interval *arr, int start, int end, double target)
{
  int left = start, right = end, mid;

  while (left < right)
  {
    mid = (left + right) / 2;
    if (mid == left)
    {
      if (arr[right].percentage <= target)
      {
        return right;
      }
      else
        return left;
    }

    if (arr[mid].percentage > target)
    {
      right = mid;
    }
    else
    {
      left = mid;
    }
  }
  // left == right
  return left;
}

Solution *solutionCreate(int n, int *blacklist, int blacklistSize)
{
  Solution *obj = (Solution *)calloc(1, sizeof(Solution));
  obj->intervals = (Interval *)calloc(blacklistSize + 1, sizeof(Interval));
  double totalPercentage = 0.0, totalWidth = n - blacklistSize;
  int leftBorder = 0;

  qsort(blacklist, blacklistSize, sizeof(int), cmp);

  for (int i = 0; i < blacklistSize; i++)
  {
    if (blacklist[i] != leftBorder)
    {
      obj->intervals[obj->intervalsSize++] = (Interval){0.0, leftBorder, blacklist[i] - 1};
    } 
    leftBorder = blacklist[i] + 1;
  }
  if (leftBorder < n)
  {
    obj->intervals[obj->intervalsSize++] = (Interval){0.0, leftBorder, n - 1};
  }

  // Record cumulative percentage of each interval by its width
  for (int i = 0; i < obj->intervalsSize; i++)
  {
    obj->intervals[i].percentage = totalPercentage;
    totalPercentage += (double)(obj->intervals[i].rightBorder - obj->intervals[i].leftBorder + 1) / totalWidth;
  }
  return obj;
}

int solutionPick(Solution *obj)
{
  double percentage = (double)rand() / RAND_MAX;
  // Find the interval that the percentage falls into by binary search
  int index = findIndex(obj->intervals, 0, obj->intervalsSize - 1, percentage);
  return getRandom(&obj->intervals[index]);
}

void solutionFree(Solution *obj)
{
  free(obj->intervals);
  free(obj);
}

```
['C']