2. A team has N people and they are trying to reach the same destination. They m
ID: 3705457 • Letter: 2
Question
2. A team has N people and they are trying to reach the same destination. They must first cross a bridge with distance B and then run on a wide road with distance R (wide enough for all N people to run on at the same time) to reach the destination. That is, they can run in parallel on the road. However, the bridge only allows one person to cross at a time. Each person i has the speed s, to cross the bridge and the running speed v, to get to the destination from the road. There exists an optimal ordering for crossing the bridge that reduces the total time it takes for the whole team to reach the destination. Give an efficient algorithm which finds a schedule with the shortest team completion time. Implement a programin Go which reads N. B. R, si (l i N), and v, (1 iExplanation / Answer
I think the best way to solve this problem is they should start running together on the bridge at t=0, and the order of the runners is descending order of speed in the bridge(s). If they start running in any other combinational order there is a possibility of an overtaking scenario, but the bridge is so narrow that at a time only one runner can run at a particular position i.e. if a speed runner runs after a slow runner then the fast runner have to slow down because to avoid the bridge condition so that the average time of reaching at the end might affect, so only one solution is there; make a queue according to there speed on the bridge and allow them to run .
the algorithm is very simple; create a link list which has three nodes;
one contains the s value and one contains the v value of each player.
struct node
{
int bridge_speed;
int rode_speed;
struct node *next;
};
You may need the following function to implement
/* Function to insert a node at the begining of a linked lsit */
void insertAtTheBegin(struct Node **start_ref, int data)
{
struct Node *ptr1 = (struct Node*)malloc(sizeof(struct Node));
ptr1->data = data;
ptr1->next = *start_ref;
*start_ref = ptr1;
}
/* Bubble sort the given linked lsit */
void bubbleSort(struct Node *start)
{
int swapped, i;
struct Node *ptr1;
struct Node *lptr = NULL;
/* Checking for empty list */
if (ptr1 == NULL)
return;
do
{
swapped = 0;
ptr1 = start;
while (ptr1->next != lptr)
{
if (ptr1->data > ptr1->next->data)
{
swap(ptr1, ptr1->next);
swapped = 1;
}
ptr1 = ptr1->next;
}
lptr = ptr1;
}
while (swapped);
}
/* function to swap data between two nodes a and b*/
void swap(struct Node *a struct Node *b)
{
int temp = a->data;
a->data = b->data;
b->data = temp;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.