educative.io

Is priority queue necessary?

Courses
,
#1

Wondering if the heap is necessary? I am merging overlapping intervals and keeping track of maxSoFar. This seems to work with the given use cases, but not sure if I might be missing some other important corner case? Any inputs would be welcomed.

public static int findMaxCPULoad(List<Job> jobs) {
    Collections.sort(jobs, Comparator.comparing(e -> e.start));
    Job interval1 = jobs.get(0);
    int maxSoFar = interval1.cpuLoad;
    for (int i = 1; i < jobs.size(); i++) {
        Job interval2 = jobs.get(i);
        if (interval2.start <= interval1.end) { // In case of overlap, find max load and calculate next interval
            interval1 = new Job(Math.min(interval1.start, interval2.start), Math.max(interval1.end, interval2.end), interval1.cpuLoad + interval2.cpuLoad);
            maxSoFar = Math.max(maxSoFar, interval1.cpuLoad);
        } else {
            maxSoFar = Math.max(maxSoFar, interval2.cpuLoad);
            interval1 = interval2;
        }
    }
    return maxSoFar;
}
1 Like
#2

One thing to add is the empty check in the beginning and return -1 if empty. This will avoid Array index related exceptions

#3

I have the same question! I don’t see the need of a priorityQueue here.
this is my solution and it works just fine for the given testcases. I assume it can work for any given input.

    public static int findMaxCPULoad(List<Job> jobs) {
    // TODO: Write your code here
    Collections.sort(jobs , (a, b) -> Integer.compare(a.start, b.start));
    int maxLoad = 0;

    for (int i = 0; i < jobs.size(); i++) {
      Job currJob = jobs.get(i);
      int currLoad = currJob.cpuLoad;

      int j = i + 1;
      while( j < jobs.size() && currJob.end > jobs.get(j).start) {
        currLoad += jobs.get(j).cpuLoad;
        j++;
      }
      maxLoad = Math.max( maxLoad, currLoad);
    }

    return maxLoad;
  }

Can anyone help ?