CODEWITHSUNDEEP
javascheduling
sgowd
sgowd

Reputation: 2260

Task scheduling algorithm with individual deadline

I have n tasks, each has a specific deadline and time it takes to complete. However, I cannot complete all tasks with in their deadlines. I need to arrange these tasks in such a way to minimize the task's deadline over shoot time. Consider this case(left values are dead lines and right side values are time the task takes):
2 2
1 1
4 3
These three tasks can be done optimally like this:

time 1 : task 2 - task1 complete; 0 overshoot for task2
time 2 : task 1
time 3 : task 1 - task2 complete; 1 overshoot for task1
time 4 : task 3
time 5 : task 3
time 6 : task 3 - task3 complete; 3 overshoot for task3

I need a faster algorithm for this; my goal is to find maximum overshoot of all overshoots(in above case its 3). Right now, i am sorting the tasks based on deadlines but its not fast, as when a new task is added, I should sort the whole list. Is there any other way?

After Lawrey's suggestion, I am using PriorityQueue but it is not giving me exact sorting. This is my code:

class Compare2DArray implements Comparator<int[]> {
public int compare(int a[], int b[]) {
    for (int i = 0; i < a.length && i < b.length; i++)
        if (a[i] != b[i])
            return a[i] - b[i];
    return a.length - b.length;
}
}

public class MyClass{
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        int numberOfInputs= scan.nextInt();
        PriorityQueue<int[]> inputsList = new PriorityQueue<int[]>(numberOfInputs,new Compare2DArray());
        for (int i = 0; i < numberOfInputs; i++) {
            int[] input = new int[2];
            input[0] = scan.nextInt();
            input[1] = scan.nextInt();
            inputsList.add(input);

        }
    }

But this is sorting this queue of arrays

2 2
1 1
4 3
10 1
2 1

as

1 1
2 1
4 3
10 1
2 2

instead of

1 1
2 1
2 2
4 3
10 1

The same comparator works fine over List sorting. I am not getting whats wrong with PriorityQueue

Upvotes: 2

Views: 5067

Answers (3)

peeyush1234
peeyush1234

Reputation: 41

Priority Queue is implemented using heaps. Hence, when you scan over the elements of priority queue it will not guarantee that it will give you all elements in sorted order. That is why you are not getting the desired sorted array.

I also faced the same problem for the question. I ended up using multimap in c++. But still the time complexity didn't improved much.

Upvotes: 4

Rachee Singh
Rachee Singh

Reputation: 106

I was attempting the same question (Its from interviewstreet, I suppose). Did you get this order:

1 1, 2 1, 4 3, 10 1, 2 2

when you printed the heap? Did you try popping items off the heap one by one and check their order? I am saying this since my implementation is in python and when I print the heap, I get the same order as you were saying. But that is not the point here, I think, since when I pop elements of the heap, one by one, I get a proper order that is:

1 1, 2 1, 2 2, 4 3, 10 1

Here is what my code in python looks like: (I am using the heapq library for implementing the priority queue) To add elements to the heap:

[deadline, minutes] = map( int, raw_input().split() )
heapq.heappush( heap, ( deadline, minutes ) )

To remove them from the heap:

d, m = heapq.heappop( heap )

Here is the output I get when I print the heap, followed by popping elements from the heap step by step:

Heap: [(1, 1), (2, 1), (4, 3), (10, 1), (2, 2)] Job taken: 1 1 Job taken: 2 1 Job taken: 2 2 Job taken: 4 3 Job taken: 10 1

Hope that helps!

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533442

Unless you have a really long list of tasks, e.g. millions, it shouldn't be taking that long.

However, what you need is likely to be a PriorityQueue which has O(1) add and O(ln N) take

Upvotes: 1

Related Questions