Amazon OA 2 Round Robin 求助

leoyue 发表于 2016-1-4 23:34
不。。。是他们写的java跑出来也是1。。。但是我改写成c++就错了

额。。。那那个1.25是哪来的 诡异

pengzewen37 发表于 2016-1-5 12:36
额。。。那那个1.25是哪来的 诡异

我写错了。。。

class Process{
  int arriveTime;
  int executeTime;
  Process(int arr, int exe){
    this.arriveTime = arr;
    this.executeTime = exe;
}
}

public static double roundRobin(int[] arrive, int[] execute, int q){
                if(arrive == null || execute == null || arrive.length != execute.length)
                        return 0.0;
                int len = arrive.length;
                int currTime = 0;
                int waitTime = 0;
                int i = 0;
                PriorityQueue<Process> pq = new PriorityQueue<Process>(len, new Comparator<Process>(){
                        @Override
                        public int compare(Process p1, Process p2){
                                return p1.arriveTime - p2.arriveTime;
                               
                        }

                       
                });
               
                while(!pq.isEmpty()  || i < len){
                        if(!pq.isEmpty()){
                                Process tmp = pq.poll();
                                waitTime += currTime - tmp.arriveTime;
                                if(tmp.executeTime > q){
                                        currTime += q;
                                        pq.offer(new Process(currTime,tmp.executeTime - q));
                                }else{
                                        currTime += tmp.executeTime;
                                }
                                for(; i < len; i++){
                                        if(arrive[i] <= currTime){
                                                pq.offer(new Process(arrive[i],execute[i]));
                                        }else
                                                break;
                                }
                        }else{
                                currTime = arrive[i];
                                pq.offer(new Process(arrive[i],execute[i]));
                                i++;
                        }
                }
                return waitTime * 1.0 / len;
               
        }

补充内容 (2016-1-5 13:15):
不知道对不对，还望楼主指出

BrilliantBean 发表于 2016-1-5 13:13
class Process{
  int arriveTime;
  int executeTime;

else currTime += temp.executeTime改成 curTime += Math.min(tmp.executeTime, q)试试呢  不要写else 因为不管execute多久 都是要更新curTime的
还有就是 那个if () {} 应该放在for loop的后面

public class Event{
            int arrive;
            int execute;
            public Event(int arrive,int execute){
                    this.arrive = arrive;
                    this.execute = execute;
            }
    }
   
    public double roundRobin(int[] arrive,int[] execute,int limit){
            int n = arrive.length;
            Event[] events = new Event[n];
            for(int i = 0;i<n;i++){
                    events[i] = new Event(arrive[i],execute[i]);
            }
            Arrays.sort(events,new Comparator<Event>(){
                    public int compare(Event e1,Event e2){
                            return e1.arrive-e2.arrive;
                    }
            });
            int nextIndex = 1,currTime = events[0].arrive,waitTime = 0;
            Queue<Event> queue = new LinkedList<>();
            queue.offer(events[0]);
            while(!queue.isEmpty()||nextIndex<n){
                    if(!queue.isEmpty()){
                            Event currEvent = queue.poll();
                            waitTime += currTime-currEvent.arrive;
                            boolean finish = true;
                            if(currEvent.execute<=limit){
                                    currTime += currEvent.execute;       
                            }else{
                                    currTime += limit;
                                    finish = false;
                            }
                           
                            for(int i = nextIndex;i<n;i++){
                                    if(events[i].arrive<=currTime){
                                            queue.offer(events[i]);
                                            nextIndex = i+1;
                                    }else{
                                            break;
                                    }
                            }
                           
                              if(!finish){
                                    Event remain = new Event(currTime,currEvent.execute-limit);
                                    queue.offer(remain);
                            }
                    }else{
                            currTime = events[nextIndex].arrive;
                            queue.offer(events[nextIndex]);
                            nextIndex++;
                    }
                     
            }
            return waitTime*1.0/n;
    }

这个代码debug过很多test case 应该没问题

你的是对的，你看的面经不对

request time: [0,2,4,5]
duration: [7,4,1,4]
q=3
average waiting time : 7

地理给的面经运行出来是7，但我自己手算是6.25啊~
很捉急啊，要考oa2了，谁能给我解释一下啊，谢谢啦！！！

leoyue 发表于 2016-1-5 12:23
http://www.1point3acres.com/bbs/thread-144891-1-1.html 给的附件，还有另一个之前的总结贴吧，反正算 ...

lz你好。请问改c++的时候，数组的长度你是怎么得到的呀?还请赐教哈。
nextProIdx < arrive.length

llsshh1128 发表于 2016-2-23 07:08
request time: [0,2,4,5]
duration: [7,4,1,4]
q=3

需要注意的是： 当第一次执行完task 0的时候，task 2 和task 3还没到来，所以task0的第二次执行在task2之前，task的执行顺序如下： task queue
0
1，0
0，2，3，1
2，3，1，0
3，1，0
1，0，3
0，3
3