Question

导入java.util。*;

公共类崩溃{

   公共静态void main（String [] args）{

/*************************************************************************
       * Q6:
       * Do you know how mobile phone works? They connect to base station to
       * send and receive messages and voice packages. Each base station will
       * handle a large number of smart phones' request. Assume one base station
       * can only process one request from one mobile phone. Each request need
       * a certain time to be processed. When the base station is busy, incoming
       * request should wait in line. Assume that a base station has a maximum
       * capacity N, which indicates that it can only keep N requests waiting
       * in the line, otherwise, it will crash. Given an array of incoming
       * request time and another array indicates corresponding process times.
       * Please implement the crash method in Q6 for the simulation of base station.
       * The method will return the crash time for the base station. If the system
       * will not crash for the given requests, return -1.
       * For example, given
       * arrival time = [1,4,4,5,7,10,12] and task required time = [3,9,12,9,10,4,3]
       * if the maximum capacity N=1, the result of crash time will be 5
       * if the maximum capacity N=2, the result of crash time will be 7
       * if the maximum capacity N=3, the result of crash time will be 10
       * if the maximum capacity N=4, the result of crash time will be 12
       * if the maximum capacity N=5, the result of crash time will be -1
       *************************************************************************/
       int[] arrival = {1,4,4,5,7,10,12};
       int[] task= {3,9,12,9,10,4,3};
       int capacity = 3;
       System.out.println("Q6 = [25 marks] =================================");
       System.out.println(Q6.crash(arrival, task, capacity));
   }
  
}

class Q6 {
  
   public static int crash(int[] arrival, int[] task, int capacity){
      
       //TODO
       return 0;
   }
  
}

Answer 1

Q6.java

import java.util.LinkedList;
import java.util.Queue;

class Q6 {
  
public static int crash(int[] arrival, int[] task, int capacity)
{
   //Why we increase capacity? It is because 1 process is being processed and others are waiting.
   //So adding 1 for that process which is being processed
   capacity++;
  
   //Use queue to hold waiting processes
   Queue<Integer> q = new LinkedList<>();
     
   //Length of process coming in
   int len = arrival.length;
         
   int i=0;
   int head;
   int current_time = 0;
     
   //Iterate over the incoming list
   for(i=0; i<len; i++)
   {
       int end_time = arrival[i] + task[i];
       current_time = arrival[i];
         
       //We will iterate our queue and remove all process which have already finished processing
       while(!q.isEmpty())
       {
           head = q.peek();
           if(head <= current_time)
           {
               q.remove(); // process is complete. Remove it from queue.
               capacity++;
           }
           else
           {
               break;
           }
       }
         
       //If there is still capacity to hold this current process, add it to queue, else return the arrival time of this process.
       if(capacity > 0)
       {
           q.add(end_time);
           capacity --;
       }
       else
       {
           return arrival[i];
       }
   }
     
//If no crash occurred, return -1
return -1;
}
  
}

Main.java

public class Main {
  
   public static void main(String args[])
   {
   int[] arrival = {1,4,4,5,7,10,12};
   int[] task= {3,9,12,9,10,4,3};
   int capacity = 1;
   int result = Q6.crash(arrival, task, capacity);
   System.out.println("Capacity = "+capacity+" crash = "+result);
  
   capacity = 2;
   result = Q6.crash(arrival, task, capacity);
   System.out.println("Capacity = "+capacity+" crash = "+result);
     
   capacity = 3;
   result = Q6.crash(arrival, task, capacity);
   System.out.println("Capacity = "+capacity+" crash = "+result);
     
   capacity = 4;
   result = Q6.crash(arrival, task, capacity);
   System.out.println("Capacity = "+capacity+" crash = "+result);
     
   capacity = 5;
   result = Q6.crash(arrival, task, capacity);
   System.out.println("Capacity = "+capacity+" crash = "+result);
  
   }
   }

Sample I/O and output