educative.io

O(N) time complexity - Alternate solution

Courses
,
#1 
class PowerInterval {
  public start: number;
  public end: number;
  public power: number;
  constructor(start:number, end: number, power: number) {
    this.start = start;
    this.end = end;
    this.power = power;
  }
}

/**
 *
 * @param jobsUnsorted
 */
const maxPower = (jobsUnsorted: Array<PowerInterval>): number => {
  const jobs = jobsUnsorted.sort((a, b) => a.start - b.start);
  const length = jobs.length;
  let start = jobs[0].start;
  let end = jobs[0].end;
  let max = jobs[0].power;
  for (let index = 1; index < length; index += 1) {
    const previous = jobs[index - 1];
    const current = jobs[index];
    if (current.start < end) {
      // overlap
      end = Math.max(end, current.end)
      max += current.power;
    } else {
      max = Math.max(max, current.power);
    }
  }
  return max;
}

Time Complexity O(N)

Any thoughts?

1 Like
#2

I also came up with this, it’s N log N since you do need to do the sort, but it followed the examples more closely than the first challenge problem, which was a huge leap from the examples

def find_max_cpu_load(jobs):
  jobs.sort(key=lambda job: job.start)
  max_load = 0
  end = jobs[0].end
  load = jobs[0].cpu_load
  for idx in range(1, len(jobs)):
    if jobs[idx].start < end:
      end = max(jobs[idx].end, end)
      load = load + jobs[idx].cpu_load
    else:
      max_load = max(max_load, load)
      end = jobs[idx].end
      load = jobs[idx].cpu_load
  return max(max_load, load)
1 Like
#3

Those solutions will only work on the test data that’s provided but not in other situations. For example, with this data:

console.log(`"Maximum CPU load at any time: ${find_max_cpu_load(
  [new Job(1, 4, 2), new Job(2, 4, 1), new Job(3, 6, 5), new Job(5, 7, 10)])}`)

The correct answer is 15 from the intersection of the jobs (3,6,5) and (5,7,10). However those solutions will result in a max load of 18 (the sum of all the jobs), which is incorrect. The (5,7) does not intersect with the first two jobs, but using the condition (current.start < end) will add it to your ongoing total because the previous job at (3,6) does intersect with the first two jobs, and this code does not account for the fact the previous two jobs had ended.

I also came up with a solution that only worked with the provided test data, but reading more about the heap solution I see why it is necessary. I wish the course gave some sort of preparation for problems that required heaps in the solution.

5 Likes
#4

ah I see, thanks for the explanation! Yes there is a huge gap between the example problems and the challenge problems which they should cover, and your example dataset should be included

#5

Here is another code which runs in O(n) and gives correct result. Mind you this is in Java. Is there anything wrong with below code?

public static int findMaxCPULoad(List<Job> jobs) {
        int minStart = jobs.stream().min(Comparator.comparingInt(o -> o.start)).get().start;
        int maxEnd = jobs.stream().max(Comparator.comparingInt(o -> o.end)).get().end;
        int[] rooms = new int[maxEnd - minStart + 1];

        for (Job job : jobs) {
            rooms[job.start - minStart] += job.cpuLoad;
            rooms[job.end - minStart] -= job.cpuLoad;
        }

        int count = 0;
        int max = 0;
        for (int room : rooms) {
            count += room;
            max = Math.max(max, count);
        }

        return max;
    }
#6

Got the idea from a youtube video-- this solution is to record the start and end time separately and use two pointers to to compare the starting and ending time to decide how many CUP is used at the same time. It passes all the test cases, any idea?

find_max_cpu_load = function(jobs) {
  jobs.sort((a,b)=>a.start-b.start)

  let start = [];
  let end = [];

  jobs.forEach(e => {
    start.push([e.start,e.cpu_load])
    end.push([e.end, e.cpu_load])
    }
  )
  end.sort((a,b)=>a[0]-b[0]);

  let count = 0,
    p1 = 0,
      p2 = 0,
        res = 0;

  while (p1 < start.length) {
    if (start[p1][0]<end[p2][0]){
      count += start[p1][1];
      p1++;
    } else {
      count -= end[p2][1];
      p2++;
    }
    res = Math.max(res,count)
  }
  return res;
};