Algorithm to find order in which tasks end given start time and duration

Question

I recently attended an interview in which I was asked this question:

Given start time in an array: [1, 2, 3, 2] and their durations [3, 4, 4, 3]

Find and return the order in which the task get completed. For this example end time are : [4, 6, 7, 5] so the value returned should be [1, 3, 4, 2].

My approach/solution:

Create a data-structure to represent each class as Task object having following attributes:

1. Start time
2. End time
3. Duration
4. Finish Index

Then sort the array on end time of each object. Compare each element with original array index and return the finish index in the original task order.

Please suggest any better solutions. Implementation of this approach is difficult to achieve without errors in an interview( using whiteboard and marker). what would be the easiest way to implement this, if no better solution is possible. Better solution = Better time complexity.

Answer 1

Disclaimer: I base this answer on the idea that this problem cannot be solved without any sorting

Your solution to the problem sounds fine to be honest. The problem describes that the result should be in a certain ordering, meaning that it is impossible to find a solution that is faster than O(n log n), guaranteed.

This is because it is known that there cannot exist an algorithm or program that can sort a list of sortable elements with a complexity smaller than O(n log n).

This means that if your solution runs in O(n log n), your solution is optimal. If I were you, I'd mention this property about your solution in your interview, as it shows that you not only understand that you solved the problem, but also know that there can't be a solution that is better.

If you have to actually implement this, just practice it a couple of times.

Answer 2

Let's say you have your original collection (such as an array) created as follows (pseudo-code, obviously):

create collection first[] with elements (starttime, duration)
first.append (1, 3)
first.append (2, 4)
first.append (3, 4)
first.append (2, 3)

This gives you the collection of (starttime, duration) tuples first = [(1,3), (2,4), (3,4), (2,3)].

You can then do what you wish with a separate structure containing just two things:

• the index into the current structure.
• the calculated end time.

Initially, populate and array of this new structure second so that the indexes match the original array first, as follows:

create array second[] with elements (firstindex, endtime)
for each index in first.indexes:
    second.append (index, first[index].starttime + first[index].duration)

This gives you the collection of (firstindex, endtime) tuples second = [(1,4), (2,6), (3,7), (4,5)] (we assume here that the collections are one-based rather than zero-based).

Then you go ahead and sort the second array based on the end time, giving you second = [(1,4), (4,5), (2,6), (3,7)].

Then you can get at the tasks in completion order with code like:

for each index in second.indexes:
    output "task # ", second[index].firstindex
    output " starts at, " first[second[index].firstindex].starttime
    output " duration, " first[second[index].firstindex].duration
    output " ends at ", second[index].endtime, new-line

The output of that will be:

task # 1 starts at 1 duration 3 ends at 4
task # 4 starts at 2 duration 3 ends at 5
task # 2 starts at 2 duration 4 ends at 6
task # 3 starts at 3 duration 4 ends at 7

Answer 3

The simplest and fastest solution >

create two arrays :

finaltime array : [4, 6, 7, 5]

index array : [0,1,2,3]

Sort the finaltime array with quicksort (or insert sort, if you can be sure, that the array will be very small = less than 10 numbers), whenever you switch finaltime array elements, switch the index array also.

When finaltime is ordered, the index array holds the result.

Answer 4

Your solution sounds OK, but you don't really need some of the fields on the object, nor a custom object at all, in fact.

Since you've tagged it specifically for Java:

int[] getCompletionOrder(int[] startTimes, int[] durations) {
  // Check that startTimes.length == durations.length.
  Integer[] indexes = new Integer[startTimes.length];
  for (int i = 0; i < indexes.length; ++i) {
    indexes[i] = i;
  }
  Arrays.sort(indexes, new Comparator<Integer, Integer>() {
    @Override public int compare(Integer a, Integer b) {
      return Integer.compare(
          startTimes[a] + durations[a],
          startTimes[b] + durations[b]);
    }
  });
  int[] result = new int[startTimes.length];
  for (int i = 0; i < result.length; ++i) {
    // In your question, your task indexes are 1-based, for some reason.
    result[i] = indexes[i] + 1;
  }
  return result;
}

Answer 5

I create a task object holding two members, a start time and a duration. The task object has a method that computes the end time based on the start time and the duration.

Furthermore, I create a comparator of tasks (see below) that compares two tasks by their end time.

The main class then creates these four tasks, puts them into an array list which is sorted using the comparator created above.

Class Task:

public class Task {

      private String m_name;
      private double m_startTime;
      private double m_duration;

      ...

      public double calculateEndTime() {
            return m_startTime + m_duration;
      }
}

Class TaskComparator:

public class TaskComparator implements Comparator<Task>{
    @Override
    public int compare(Task t1, Task t2) {
        if (t1 == null || t2 == null) {
            return 0;
        }
    return Double.compare(t1.calculateEndTime(), t2.calculateEndTime());
}

Main method:

public void go() {
    List<Task> tasks = new ArrayList<Task>();
    tasks.add(new Task("First Task", 1, 3));
    tasks.add(new Task("Second Task", 2, 4));
    tasks.add(new Task("Third Task", 3, 4));
    tasks.add(new Task("Fourth Task", 2, 3));
    Collections.sort(tasks, new TaskComparator());
    for (Task task : tasks) {
        System.out.println(task.toString());
    }
}

Answer 6

New Version After Glubus comments I understand that my previous solution is not so good as I could think. But for sake of insanity I propose a new version that:

• not require sort

• assign same place to task that have the same end time

  int[] calculateCompletionsOrder(int[] starttimes, int[] durations) {
  
      // the key is the endtime (sorted ascending), the value is a list of the taskid with corresponding endtime  
      TreeMap<Integer, List<Integer>> set = new TreeMap<Integer, List<Integer>>();
  
      // first iteration is needed to calucate endtimes
      for (int taskId = 0; taskId < starttimes.length; taskId++) { // time complexity O(nlogn)
          // calculate end time for the current task
          int endtime = starttimes[taskId] + durations[taskId];
          // add the task to the list of task with same end time
          List<Integer> taskIds = set.get(endtime); // time complexity O(logn)
          if (taskIds == null) {
              taskIds = new ArrayList<Integer>();
              set.put(endtime, taskIds); // time complexity O(logn)
          }
          taskIds.add(taskId); // time complexity O(1)
      }
  
      // now calculate the order each task get completed
      int[] completionorders = new int[starttimes.length];
      int order = 1;
      // iterate over end times in ascending order
      for (List<Integer> taskIds : set.values()) { // time complexity O(n)
          for (int taskId : taskIds) {
              // set the completion order for the selected task
              completionorders[taskId] = order;
          }
          // increment order for next group of tasks with next end time 
          order++;
      }
  
      return completionorders;
  }
  

The cost of sort is distibuted on each insert. Final complexity is for best, average, worst case O(nlogn).

Old Version

The question is "Find and return the order in which the task get completed.".

The question does not state anything about how the order should be represented. I mean nothing like: "if you have four elements order should be represented from natural number between 1 an 4".

So in my solution the order is represented with integer (..., -3, -2, -1, 0, 1, 2, 3, ...). Also "order" does not imply that two numbers are consecutives.

• Input:

  • start-time: [1, 2, 3, 2]
  • durations : [3, 4, 4, 3]

• Algorithm (First phase): calculate end time

  max-end-time = 0;
  for (int i = 0; i < start-time.length; ++i) {
     end-time[i] = start-time[i] + durations[i];
     max-end-time = max-end-time > end-time[i] ? max-end-time : end-time[i];
  }
  

• At the end of first phase your output is:

  • end-time: [4, 6, 7, 5]
  • max-end-time: 7

• Algorithm (Second phase): calculate finish order

  for (int i = 0; i < end-time.length; ++i) {
     order[i] = end-time[i] - max-end-time;           
  }
  

At the end of second phase your finish order array is : [-3, -1, 0, -2].

So task 0 is the first, task 2 is the third, task 3 is the fourth, task 4 is the second, or in another form: [1, 3, 4, 2].

Complexity: if n is the number of task the algorithm do n + n = 2n iterations. So this algorithm is O(n).