PQ

package weblab;

import java.util.*;


class Task implements Comparable<Task> {
    int start, end;

    public Task(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Task o) {
        return Integer.compare(this.start, o.start);
    }
}

class Solution {


    /**
     * @param n number of researchers
     * @param m number of minutes after which workstations lock themselves
     * @param start start times of jobs 1 through n. NB: you should ignore start[0]
     * @param duration duration of jobs 1 through n. NB: you should ignore duration[0]
     * @return the number of unlocks that can be saved.
     */
    public static int solve(int n, int m, int[] start, int[] duration) {
      Task[] tasks = new Task[n];
      for (int i = 1; i <= n; ++i)
        tasks[i-1] = new Task(start[i], start[i] + duration[i]);

      Arrays.sort(tasks); // increasing by start time


      PriorityQueue<Integer> pq = new PriorityQueue<>();
      int locks = 0;

      for (Task task: tasks) {

        if (pq.isEmpty()) {
          pq.add(task.end);
          locks ++;
          continue;
        }

        while (!pq.isEmpty() && task.start > pq.peek() + m) // machine won't be used anymore
          pq.poll();

        if (pq.isEmpty()) {
          pq.add(task.end);
          locks ++;
        }
        else
          if (task.start >= pq.peek())
          {
            pq.poll();
            pq.add(task.end);
          }
        else {
          pq.add(task.end);
          locks ++;
        }


      }

      return n - locks;

    }
}