aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-07-28 17:41:01 -0600
committerJack Sangdahl <[email protected]>2024-07-28 17:41:01 -0600
commit09570f171a5c9a6540cd7350e0fed3b71b1472ce (patch)
tree39704dd971add336f2f8ee6e9d562840bf50f1c1
parent9b1687331bb6385e4ae676b1be5482d3c2156fd4 (diff)
downloadleetcode-09570f171a5c9a6540cd7350e0fed3b71b1472ce.tar.gz
leetcode-09570f171a5c9a6540cd7350e0fed3b71b1472ce.zip
2045. second minimum time to reach destination
-rw-r--r--second_min_time_dest.c186
-rw-r--r--second_min_time_dest.py56
2 files changed, 242 insertions, 0 deletions
diff --git a/second_min_time_dest.c b/second_min_time_dest.c
new file mode 100644
index 0000000..02852ea
--- /dev/null
+++ b/second_min_time_dest.c
@@ -0,0 +1,186 @@
+// 2045. Second Minimum Time to Reach Destination
+#include "leetcode.h"
+
+/*
+ * a city is represented as a bi directional connected graph with 'n' vertices
+ * where each vertex is labeled from 1 to 'n' inclusively. the edges in the
+ * graph are represented as a 2d integer array 'edges' where each 'edges[i] =
+ * [ui, vi]' denotes a bi directional edge between vertex 'ui' and vertex 'vi'.
+ * every vertex pair is connected by at most one edge, and no vertex has an edge
+ * to itself. the time taken to traverse any edge is 'time' minutes. each vertex
+ * has a traffic signal which changes its colour from green to red and vice
+ * versa every 'change' minutes. all signals change at the same time. you can
+ * entre a vertex at any time, but can leave a vertex only when the signal is
+ * green. you cannot wait at a vertex if the signal is green.
+ */
+
+struct state {
+ int node;
+ int time;
+};
+
+struct min_heap {
+ struct state *data;
+ int size;
+ int capacity;
+};
+
+void swap(struct state *a, struct state *b) {
+ struct state tmp = *a;
+ *a = *b;
+ *b = tmp;
+}
+
+struct min_heap *create_min_heap(int capacity) {
+ struct min_heap *heap = (struct min_heap *)malloc(sizeof(struct min_heap));
+ heap->data = (struct state *)malloc(capacity * sizeof(struct state));
+ heap->size = 0;
+ heap->capacity = capacity;
+ return heap;
+}
+
+void min_heapify(struct min_heap *heap, int idx) {
+ int smallest = idx, left = 2 * idx + 1, right = 2 * idx + 2;
+ if (left < heap->size && heap->data[left].time < heap->data[smallest].time)
+ smallest = left;
+ if (right < heap->size && heap->data[right].time < heap->data[smallest].time)
+ smallest = right;
+ if (smallest != idx) {
+ swap(&heap->data[idx], &heap->data[smallest]);
+ min_heapify(heap, smallest);
+ }
+}
+
+struct state extract_min(struct min_heap *heap) {
+ if (heap->size <= 0)
+ return (struct state){-1, -1};
+ if (heap->size == 1) {
+ heap->size--;
+ return heap->data[0];
+ }
+ struct state root = heap->data[0];
+ heap->data[0] = heap->data[heap->size - 1];
+ heap->size--;
+ min_heapify(heap, 0);
+ return root;
+}
+
+void insert_min_heap(struct min_heap *heap, struct state k) {
+ if (heap->size == heap->capacity) {
+ heap->capacity *= 2;
+ heap->data = (struct state *)realloc(heap->data,
+ heap->capacity * sizeof(struct state));
+ }
+ heap->size++;
+ int i = heap->size - 1;
+ heap->data[i] = k;
+ while (i && heap->data[(i - 1) / 2].time > heap->data[i].time) {
+ swap(&heap->data[i], &heap->data[(i - 1) / 2]);
+ i = (i - 1) / 2;
+ }
+}
+
+void free_min_heap(struct min_heap *heap) {
+ free(heap->data);
+ free(heap);
+}
+
+struct node {
+ int val;
+ struct node *next;
+};
+
+struct graph {
+ struct node **heads;
+ int *sizes;
+ int size;
+};
+
+struct graph *create_graph(int n) {
+ struct graph *g = (struct graph *)malloc(sizeof(struct graph));
+ g->heads = (struct node **)malloc((n + 1) * sizeof(struct node *));
+ g->sizes = (int *)calloc(n + 1, sizeof(int));
+ g->size = n;
+ for (int i = 0; i <= n; i++)
+ g->heads[i] = NULL;
+ return g;
+}
+
+void add_edges(struct graph *g, int u, int v) {
+ struct node *n = (struct node *)malloc(sizeof(struct node));
+ n->val = v;
+ n->next = g->heads[u];
+ g->heads[u] = n;
+ n = (struct node *)malloc(sizeof(struct node));
+ n->val = u;
+ n->next = g->heads[v];
+ g->heads[v] = n;
+ g->sizes[u]++;
+ g->sizes[v]++;
+}
+
+void free_graph(struct graph *g) {
+ for (int i = 0; i <= g->size; i++) {
+ struct node *head = g->heads[i];
+ while (head) {
+ struct node *tmp = head;
+ head = head->next;
+ free(tmp);
+ }
+ }
+ free(g->heads);
+ free(g->sizes);
+ free(g);
+}
+
+int secondMinimum(int n, int **edges, int edgesSize, int *edgesColSize,
+ int time, int change) {
+ struct graph *g = create_graph(n);
+ for (int i = 0; i < edgesSize; i++)
+ add_edges(g, edges[i][0], edges[i][1]);
+ int *min_time = (int *)malloc((n + 1) * sizeof(int));
+ int *second_min_time = (int *)malloc((n + 1) * sizeof(int));
+ for (int i = 0; i <= n; i++) {
+ min_time[i] = INT_MAX;
+ second_min_time[i] = INT_MAX;
+ }
+ struct min_heap *pq = create_min_heap(edgesSize * 2);
+ insert_min_heap(pq, (struct state){1, 0});
+ min_time[1] = 0;
+ while (pq->size) {
+ struct state curr = extract_min(pq);
+ int curr_node = curr.node;
+ int curr_time = curr.time;
+ struct node *neighbour_node = g->heads[curr_node];
+ while (neighbour_node) {
+ int neighbour = neighbour_node->val, wait_time = 0;
+ if ((curr_time / change) % 2 == 1)
+ wait_time = change = (curr_time % change);
+ int next_time = curr_time + time + wait_time;
+ if (next_time < min_time[neighbour]) {
+ second_min_time[neighbour] = min_time[neighbour];
+ min_time[neighbour] = next_time;
+ insert_min_heap(pq, (struct state){neighbour, next_time});
+ } else if (next_time > min_time[neighbour] &&
+ next_time < second_min_time[neighbour]) {
+ second_min_time[neighbour] = next_time;
+ insert_min_heap(pq, (struct state){neighbour, next_time});
+ }
+ neighbour_node = neighbour_node->next;
+ }
+ }
+ int ans = second_min_time[n];
+ free(min_time), free(second_min_time);
+ free_min_heap(pq);
+ free_graph(g);
+ return ans;
+}
+
+int main() {
+ int e1[5][2] = {{1, 2}, {1, 3}, {1, 4}, {3, 4}, {4, 5}}, e2[1][2] = {{1, 2}};
+ int ecs1 = 5, ecs2 = 1;
+ printf("%d\n", secondMinimum(5, (int **)e1, ARRAY_SIZE(e1), &ecs1, 3,
+ 5)); // expect: 13
+ printf("%d\n", secondMinimum(2, (int **)e2, ARRAY_SIZE(e2), &ecs2, 3,
+ 2)); // expect: 11
+}
diff --git a/second_min_time_dest.py b/second_min_time_dest.py
new file mode 100644
index 0000000..adf08da
--- /dev/null
+++ b/second_min_time_dest.py
@@ -0,0 +1,56 @@
+# 2045. Second Minimum Time to Reach destination
+from collections import defaultdict
+import heapq
+from math import ceil
+
+"""
+a city is represented as a bi directional connected graph with 'n' vertices
+where each vertex is labeled from 1 to 'n' inclusively. the edges in the
+graph are represented as a 2d integer array 'edges' where each 'edges[i] =
+[ui, vi]' denotes a bi directional edge between vertex 'ui' and vertex 'vi'.
+every vertex pair is connected by at most one edge, and no vertex has an edge
+to itself. the time taken to traverse any edge is 'time' minutes. each vertex
+has a traffic signal which changes its colour from green to red and vice
+versa every 'change' minutes. all signals change at the same time. you can
+entre a vertex at any time, but can leave a vertex only when the signal is
+green. you cannot wait at a vertex if the signal is green.
+"""
+
+
+class Solution(object):
+ def secondMinimum(self, n, edges, time, change):
+ """
+ :type n: int
+ :type edges: List[List[int]]
+ :type time: int
+ :type change: int
+ :rtype: int
+ """
+ d = [[] for _ in range(n + 1)]
+ d[1] = [0]
+ g, heap = defaultdict(list), [(0, 1)]
+ for a, b in edges:
+ g[a] += [b]
+ g[b] += [a]
+ while heap:
+ min_dist, idx = heapq.heappop(heap)
+ if idx == n and len(d[n]) == 2:
+ return max(d[n])
+ for neib in g[idx]:
+ if (min_dist // change) % 2 == 0:
+ cand = min_dist + time
+ else:
+ cand = ceil(min_dist / (2 * change)) * (2 * change) + time
+ if not d[neib] or (len(d[neib]) == 1 and d[neib] != [cand]):
+ d[neib] += [cand]
+ heapq.heappush(heap, (cand, neib))
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.secondMinimum(
+ n=5, edges=[[1, 2], [1, 3], [1, 4], [3, 4], [4, 5]], time=3, change=5
+ )
+ )
+ print(obj.secondMinimum(n=2, edges=[[1, 2]], time=3, change=2))