GoldmanSachs.java

// 1 3 800
// 1 2 500
// 2 3 500
// 1 70
// 2 40
// 1 3
public static class Station {
  int city;
  int price;
  int capacity;
  public Station(int city, int price, int capacity) {
    this.city = city;
    this.price = price;
    this.capacity = capacity;
  }
}

public static class Destination {
  int city;
  int cost;
  public Destination(int city, int cost) {
    this.city = city;
    this.cost = cost;
  }
}

public static int minimumAmount(int N, int C, int[][] roads, int[][] fuels, int A, int B) {
  // visited boolean array 1 to N
  boolean[] visited = new boolean[N + 1];
  visited[A] = true;

  int[] costs = new int[N + 1];
  costs[A] = 0;

  int[] fuelPrice = new int[N + 1];
  for (int[] fuel : fuels) {
    fuelPrice[fuel[0]] = fuel[1];
  }

  // pathQueues: pq array with each element = [city, price, capacity]
  Comparator<Station> priceComparator = (s1, s2) -> {
    return s1.price < s2.price ? -1 : 1;
  };
  PriorityQueue<Station>[] pathQueues = new PriorityQueue[N + 1];
  pathQueues[A] = new PriorityQueue<>(priceComparator);
  pathQueues[A].add(new Station(A, fuelPrice[A], C));

  // make list of cities and neighbors
  ArrayList<Destination>[] neighbors = new ArrayList[N + 1];
  for (int i = 0; i < N + 1; i++) { 
    neighbors[i] = new ArrayList<Destination>(); 
  }

  for (int[] road : roads) {
    Destination dest = new Destination(road[1], road[2]);
    neighbors[road[0]].add(dest);
  }

  // queue
  Queue<Destination> queue = new LinkedList<>();
  // add city A to queue
  queue.add(new Destination(A, 0));

  while (!queue.isEmpty()) {
    Destination curCity = queue.remove();
    ArrayList<Destination> curNeighbors = neighbors[curCity.city];

    for (Destination dest : curNeighbors) {
      int fuelNeeded = dest.cost;
      int totalCost = costs[curCity.city];
      PriorityQueue<Station> curQueue = new PriorityQueue<>(pathQueues[curCity.city]);
      // trying to pay the cost with cheapest price -> higher
      while (fuelNeeded > 0) {
        if (curQueue.isEmpty()) {
          totalCost = Integer.MAX_VALUE;
          break;
        }
        System.out.println(curCity.city);
        System.out.println(pathQueues[curCity.city].size());
        Station curCheapest = curQueue.remove();
        if (curCheapest.capacity > fuelNeeded) { // this station covers the cost
          totalCost += curCheapest.price * fuelNeeded;
          curCheapest.capacity -= fuelNeeded;
          fuelNeeded = 0;
          curQueue.add(curCheapest); // still having some capacity
        } else {
          totalCost += curCheapest.price * curCheapest.capacity;
          fuelNeeded -= curCheapest.capacity;
        }
      }

      if (!visited[dest.city] || (visited[dest.city] && totalCost < costs[dest.city])) {
        costs[dest.city] = totalCost;
        if (fuelPrice[dest.city] != 0) { // current city has a station
          curQueue.add(new Station(dest.city, fuelPrice[dest.city], C));
        }
        pathQueues[dest.city] = curQueue;

        visited[dest.city] = true;
        queue.add(new Destination(dest.city, dest.cost));
      }

    }
  }

  return costs[B];
}


public static int maximizeEffective(int M, int[][] ads, int[] values) {
  int[] maxVals = new int[M + 1]; // 0 to M
  Map<Integer, ArrayList<Integer>> endToIndices = new HashMap<>();
  for (int i = 0; i < ads.length; i++) {
    int end = ads[i][1];
    if (!endToIndices.containsKey(end)) {
      endToIndices.put(end, new ArrayList<>());
    }
    endToIndices.get(end).add(i);
  }

  for (int end = 1; end <= M; end++) {
    maxVals[end] = maxVals[end - 1];
    if (endToIndices.containsKey(end)) {
      for (int index : endToIndices.get(end)) {
        int start = ads[index][0];
        int value = values[index];
        if (start > 4) {
          maxVals[end] = Math.max(maxVals[end], value + maxVals[start - 5]);
        }
      }
    }
  }
  return maxVals[M];
}


// https://leetcode.com/discuss/interview-question/699973/Goldman-Sachs-or-OA-or-Turnstile
public static int[] getTimes(int[] times, int[] directions) {
  int length = times.length;
  int[] output = new int[length];

  Queue<Integer> enterQueue = new LinkedList<>();
  Queue<Integer> exitQueue = new LinkedList<>();

  for (int i = 0; i < length; i++) {
    if (directions[i] == 0) {
      enterQueue.offer(i);
    } else {
      exitQueue.offer(i);
    }
  }
  // 0: not used, 1: entering, 2: exiting
  int state = 0; // not used by default
  int curTime = 0;
  while (true) {
    if (state == 0) {
      int nextEnter = times[enterQueue.peek()];
      int nextExit = times[exitQueue.peek()];
      if (nextEnter < nextExit) {
        state = 1;
      } else {
        state = 2;
      }
    }

    if (state == 1) { // entering
      int curEnter = enterQueue.poll();
      curTime = Math.max(times[curEnter], curTime);
      output[curEnter] = curTime++;
      if (enterQueue.isEmpty()) break;
      // if the curent time is not previous time to next enter, reset state to unused
      if (curTime < times[enterQueue.peek()]) {
        state = 0;
      }
    } else {
      int curExit= exitQueue.poll();
      curTime = Math.max(times[curExit], curTime);
      output[curExit] = curTime++;
      if (exitQueue.isEmpty()) break;
      // if the curent time is not previous time to next exit, reset state to unused
      if (curTime < times[exitQueue.peek()]) {
        state = 0;
      }
    }
  }

  while (!enterQueue.isEmpty()) {
    int curEnter = enterQueue.poll();
    curTime = Math.max(times[curEnter], curTime);
    output[curEnter] = curTime++;
  }

  while (!exitQueue.isEmpty()) {
    int curExit = exitQueue.poll();
    curTime = Math.max(times[curExit], curTime);
    output[curExit] = curTime++;
  }

  return output;
}