Сортировать выполненные запросы по времени начала

Question

С учетом запросов, поступающих в неизвестное время с идентификатором: 1. StartRequest (int id) 2. EndRequest (int id)

Мне нужно вернуть идентификаторы завершенных запросов с общим временем (endTime-startTime), отсортированным по времени начала.

Обратите внимание, что если предыдущие запросы еще не завершены, текущий запрос не возвращается, даже если он завершен.

Я попробовал наивный способ: по запросу начала я добавляю в список и по запросу конца я проверяю, есть ли запросы от начала списка до первого, который еще не завершен, и возвращаю их.

Есть ли более эффективный способ? Является ли возвращение результата в EndRequest лучшим способом?

Answer 1

используйте следующую процедуру на ваших любимых / используемых языках:

public class StartEndRequest {
private static void swap(int [] starts, int [] ends, int i, int j) {
    int temp = starts[i];
    int temp1 = ends[i];

    starts[i] = starts[j];
    ends[i] = ends[j];

    starts[j] = temp;
    ends[j] = temp1;
}
// selection sort ..
private static void sortByProcessTime(int [] starts, int [] ends) {
    for(int i=0; i<starts.length-1; i++) {
        int min = i;
        for(int j=i+1; j<starts.length; j++) {
            // swap according to execution time..
            if((ends[j] - starts[j]) > (ends[i] - starts[i]))
                min = j;
        }

        swap(starts, ends, i, min);
    }
}
private static ArrayList<ArrayList<Integer>> getFinishedProcess(int [] prevProcess, int [] starts, int [] ends){
    ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();

    for(int i=0; i<prevProcess.length; i++) {
        // add the first operation, it has no prev. operation..
        if(i == 0) {
            ArrayList<Integer> temp = new ArrayList<>();
            temp.add(starts[i]);
            temp.add(ends[i]);

            list.add(temp);
        }
        if(prevProcess[i] != -1) {
            ArrayList<Integer> temp = new ArrayList<>();
            temp.add(starts[i]);
            temp.add(ends[i]);

            list.add(temp);
        }
    }
    return list;
}
private static void blockUnfinishedProcess(int [] preProcesses, int [] starts, int [] ends) {
    for(int i=1; i<preProcesses.length; i++) {
        if(ends[i] == -1) {
            preProcesses[i] = -1;
        }
    }
}
public static void main(String[] args) {
    // use an auxiliary space to point prev. operations..
    int [] prevProcess = {-1, 0, 0, 0, 0, 0};
    int [] startReq = {2, 3, 1, 4, 6, 5};
    // i am using -1 to indicate unfinished jobs..
    int [] endReq = {7, 4, 3, -1, 8, -1};

    // sort according to execution time..
    sortByProcessTime(startReq, endReq);

    // block those operation whose prev was not finished ..
    blockUnfinishedProcess(prevProcess, startReq, endReq);

    //
    for(int i=0; i<startReq.length; i++) {
        System.out.println(startReq[i]+" -- "+endReq[i]);
    }

    // add only those operation, whose prev also executed successfully.. 
    System.out.println(getFinishedProcess(prevProcess, startReq, endReq));
}

}