CODEWITHSUNDEEP
algorithmperformancesortingdata-structures
n1989
n1989

Reputation: 95

Sort finished requests by start time

Given requests that arrive at an unknown time with id: 1. StartRequest(int id) 2. EndRequest(int id)

I need to return the ids of finished requests with the total time that it took (endTime-startTime) sorted by start time.

Note that if the previous requests are not finished yet the current request is not returned even if it's finished.

I tried the naive way: on start request, I add to a List and on end Request, I check if there are requests from the beginning of the list until the first that is not finished and return them.

Is there a more efficient way? Is returning the result on EndRequest the best way?

Upvotes: 0

Views: 154

Answers (1)

Papai from BEKOAIL
Papai from BEKOAIL

Reputation: 1539

use the following proc in your fav/used languages:

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));
}

}

Upvotes: 1

Related Questions