aboutsummaryrefslogtreecommitdiff
path: root/min_total_distance_traveled.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-30 22:15:54 -0600
committerJack Sangdahl <[email protected]>2024-10-30 22:15:54 -0600
commit45a8af12d6d2f60e1efdba06d853aaff9055193f (patch)
tree635420d1abe138bb45c2b73f49d4df8b26782c59 /min_total_distance_traveled.c
parent80c009131135eef4b5c611a9d8091abdf94a8f30 (diff)
downloadleetcode-45a8af12d6d2f60e1efdba06d853aaff9055193f.tar.gz
leetcode-45a8af12d6d2f60e1efdba06d853aaff9055193f.zip
2463. minimum total distance traveled
Diffstat (limited to 'min_total_distance_traveled.c')
-rw-r--r--min_total_distance_traveled.c245
1 files changed, 245 insertions, 0 deletions
diff --git a/min_total_distance_traveled.c b/min_total_distance_traveled.c
new file mode 100644
index 0000000..b41c3be
--- /dev/null
+++ b/min_total_distance_traveled.c
@@ -0,0 +1,245 @@
+// 2463. Minimum Total Distance Traveled
+#include "leetcode.h"
+
+/*
+ * there are some robots and factories on the x-axis. you are given an integer
+ * array 'robot' where 'robot[i]' is the position of the i'th robot. you are
+ * also given a 2d integer array 'factory' where 'factory[j] = [position_i,
+ * limit_i]' indicates that 'position[j]' is the position of the j'th factory
+ * and that the j'th factory can repair at most 'limit[j]' robots. the positions
+ * of each robot are unique. note that a robot can be in the same position as a
+ * factory initially. all the robots are initially broke; they keep moving in
+ * one direction. the direction could be the negative or positive direction of
+ * the x-axis. when a robot reaches a factory that did not reach its limit, the
+ * factory repairs the robot and it stops moving. return the minimum total
+ * distance traveled by all the robots. the test cases are generated as such
+ * that all the robots can be repaired.
+ */
+
+struct robot {
+ bool to_left;
+ int right;
+ int left;
+};
+
+struct factory {
+ int *robot_num;
+ int point;
+ int count;
+};
+
+int cmp_r(const void *a, const void *b) {
+ return *(int *)a > *(int *)b ? 1 : -1;
+}
+
+int cmp_f(const void **a, const void **b) {
+ return (*(int **)a)[0] > (*(int **)b)[0] ? 1 : -1;
+}
+
+int cost_r(int **factory, int factorySize, struct factory *f_list,
+ int right_factory) {
+ int right = 0;
+ if (right_factory == factorySize)
+ return INT_MAX;
+ while (factory[right_factory][1] <= f_list[right_factory].count) {
+ right += factory[right_factory][0] - factory[right_factory - 1][0];
+ right_factory++;
+ if (right_factory == factorySize)
+ return INT_MAX;
+ }
+ right += factory[right_factory][0] - factory[right_factory - 1][0];
+ return right;
+}
+
+void cost_f(int *robot, int **factory, struct robot *r_list,
+ struct factory *f_list, int curr, int left_factory, bool *to_left,
+ int *l, int r) {
+ if (left_factory == -1) {
+ r_list[curr].left = -1;
+ return;
+ }
+ *l += robot[curr] - factory[left_factory][0];
+ if (factory[left_factory][1] <= f_list[left_factory].count) {
+ int replace = f_list[left_factory].robot_num[f_list[left_factory].point];
+ *l -= r_list[replace].to_left ? robot[replace] - factory[left_factory][0]
+ : factory[left_factory][0] - robot[replace];
+ cost_f(robot, factory, r_list, f_list, replace, r_list[replace].left,
+ to_left, l, r);
+ if (*to_left)
+ f_list[left_factory].point++;
+ } else {
+ if (*l <= r)
+ *to_left = true;
+ }
+ if (*to_left) {
+ r_list[curr].to_left = true;
+ r_list[curr].left = left_factory - 1;
+ f_list[left_factory].robot_num[f_list[left_factory].count] = curr;
+ f_list[left_factory].count++;
+ }
+ return;
+}
+
+void to_r_change(int **factory, struct robot *r_list, struct factory *f_list,
+ int curr, int right_factory) {
+ if (factory[right_factory][1] <= f_list[right_factory].count) {
+ int replace = f_list[right_factory].robot_num[f_list[right_factory].point];
+ to_r_change(factory, r_list, f_list, replace, r_list[replace].left);
+ f_list[right_factory].point++;
+ }
+ r_list[curr].right = right_factory + 1;
+ f_list[right_factory].robot_num[f_list[right_factory].count] = curr;
+ f_list[right_factory].count++;
+ return;
+}
+
+long long minimumTotalDistance(int *robot, int robotSize, int **factory,
+ int factorySize, int *factoryColSize) {
+ qsort(robot, robotSize, sizeof(int), cmp_r);
+ qsort(factory, factorySize, sizeof(int *), cmp_f);
+ struct robot *r_list =
+ (struct robot *)malloc(robotSize * sizeof(struct robot));
+ struct factory *f_list =
+ (struct factory *)calloc(factorySize, sizeof(struct factory));
+ int point = 0, head = 0;
+ long long ans = 0;
+ for (int i = 0; i < robotSize; i++) {
+ while (point < factorySize && factory[point][0] < robot[i])
+ point++;
+ r_list[i].right = point;
+ r_list[i].left = point - 1;
+ }
+ for (int i = 0; i < factorySize; i++)
+ f_list[i].robot_num = (int *)malloc(robotSize * sizeof(int));
+ while (head < robotSize && r_list[head].left == -1) {
+ while (factory[r_list[head].right][1] == f_list[r_list[head].right].count)
+ r_list[head].right++;
+ ans += factory[r_list[head].right][0] - robot[head];
+ r_list[head].to_left = false;
+ f_list[r_list[head].right].robot_num[f_list[r_list[head].right].count] =
+ head;
+ f_list[r_list[head].right].count++;
+ head++;
+ }
+ while (head < robotSize) {
+ int left = r_list[head].left == -1
+ ? INT_MAX
+ : robot[head] - factory[r_list[head].left][0];
+ int right = r_list[head].right == factorySize
+ ? INT_MAX
+ : factory[r_list[head].right][0] - robot[head];
+ int right_factory = r_list[head].right;
+ bool to_left = false;
+ if (right_factory < factorySize) {
+ while (!factory[right_factory][1]) {
+ right_factory++;
+ if (right_factory == factorySize) {
+ right = INT_MAX;
+ break;
+ } else
+ right = factory[right_factory][0] - robot[head];
+ }
+ if (right_factory < factorySize &&
+ factory[right_factory][1] <= f_list[right_factory].count) {
+ r_list[head].to_left = false;
+ ans += right;
+ f_list[right_factory].robot_num[f_list[right_factory].count] = head;
+ f_list[right_factory].count++;
+ int replace =
+ f_list[right_factory].robot_num[f_list[right_factory].point];
+ f_list[right_factory].point++;
+ if (r_list[replace].left == -1) {
+ r_list[head].left = -1;
+ right_factory++;
+ ans += factory[right_factory][0] - factory[right_factory - 1][0];
+ while (factory[right_factory][1] <= f_list[right_factory].count) {
+ f_list[right_factory].robot_num[f_list[right_factory].count] =
+ replace;
+ replace =
+ f_list[right_factory].robot_num[f_list[right_factory].point];
+ f_list[right_factory].count++;
+ f_list[right_factory].point++;
+ right_factory++;
+ ans += factory[right_factory][0] - factory[right_factory - 1][0];
+ }
+ f_list[right_factory].robot_num[f_list[right_factory].count] =
+ replace;
+ f_list[right_factory].count++;
+ f_list[right_factory].point++;
+ } else {
+ right = cost_r(factory, factorySize, f_list, right_factory + 1);
+ left = robot[replace] - factory[right_factory][0];
+ cost_f(robot, factory, r_list, f_list, replace, r_list[replace].left,
+ &to_left, &left, right);
+ if (to_left)
+ ans += left;
+ else {
+ ans += right;
+ to_r_change(factory, r_list, f_list, replace,
+ r_list[replace].right);
+ }
+ }
+ head++;
+ continue;
+ }
+ }
+ int left_factory = r_list[head].left;
+ while (!factory[left_factory][1]) {
+ left_factory--;
+ if (left_factory >= 0) {
+ left = robot[head] - factory[left_factory][0];
+ r_list[head].left = left_factory;
+ } else {
+ left = INT_MAX;
+ r_list[head].left = left_factory;
+ break;
+ }
+ }
+ if (left_factory >= 0 &&
+ factory[left_factory][1] <= f_list[left_factory].count) {
+ int replace = f_list[left_factory].robot_num[f_list[left_factory].point];
+ left -= r_list[replace].to_left
+ ? robot[replace] - factory[left_factory][0]
+ : factory[left_factory][0] - robot[replace];
+ cost_f(robot, factory, r_list, f_list, replace, r_list[replace].left,
+ &to_left, &left, right);
+ if (to_left)
+ f_list[left_factory].point++;
+ } else {
+ if (left <= right)
+ to_left = true;
+ }
+ if (to_left) {
+ ans += left;
+ r_list[head].to_left = true;
+ r_list[head].left = left_factory - 1;
+ f_list[left_factory].robot_num[f_list[left_factory].count] = head;
+ f_list[left_factory].count++;
+ } else {
+ ans += right;
+ r_list[head].to_left = false;
+ f_list[right_factory].robot_num[f_list[right_factory].count] = head;
+ f_list[right_factory].count++;
+ }
+ head++;
+ }
+ for (int i = 0; i < factorySize; i++)
+ free(f_list[i].robot_num);
+ free(f_list), free(r_list);
+ return ans;
+}
+
+int main() {
+ int r1[] = {0, 4, 6}, f1i[2][2] = {{2, 2}, {6, 2}};
+ int r2[] = {1, -1}, f2i[2][2] = {{-2, 1}, {2, 1}};
+ struct two_d_arr f1, f2;
+ two_d_arr_init(&f1, 2, 2, f1i);
+ two_d_arr_init(&f2, 2, 2, f2i);
+ printf("%lld\n", minimumTotalDistance(r1, ARRAY_SIZE(r1), f1.arr, f1.row_size,
+ f1.col_size)); // expect: 4
+
+ printf("%lld\n", minimumTotalDistance(r2, ARRAY_SIZE(r2), f2.arr, f2.row_size,
+ f2.col_size)); // expect: 2
+ two_d_arr_free(&f1);
+ two_d_arr_free(&f2);
+}