3479. Fruits Into Baskets III

Description

You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the ith type of fruit, and baskets[j] represents the capacity of the jth basket.

From left to right, place the fruits according to these rules:

• Each fruit type must be placed in the leftmost available basket with a capacity greater than or equal to the quantity of that fruit type.
• Each basket can hold only one type of fruit.
• If a fruit type cannot be placed in any basket, it remains unplaced.

Return the number of fruit types that remain unplaced after all possible allocations are made.

 

Example 1:

Input: fruits = [4,2,5], baskets = [3,5,4]

Output: 1

Explanation:

• fruits[0] = 4 is placed in baskets[1] = 5.
• fruits[1] = 2 is placed in baskets[0] = 3.
• fruits[2] = 5 cannot be placed in baskets[2] = 4.

Since one fruit type remains unplaced, we return 1.

Example 2:

Input: fruits = [3,6,1], baskets = [6,4,7]

Output: 0

Explanation:

• fruits[0] = 3 is placed in baskets[0] = 6.
• fruits[1] = 6 cannot be placed in baskets[1] = 4 (insufficient capacity) but can be placed in the next available basket, baskets[2] = 7.
• fruits[2] = 1 is placed in baskets[1] = 4.

Since all fruits are successfully placed, we return 0.

 

Constraints:

• n == fruits.length == baskets.length
• 1 <= n <= 105
• 1 <= fruits[i], baskets[i] <= 109

 

Solutions

Solution: Segment Tree

• Time complexity: O(nlogn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} fruits
 * @param {number[]} baskets
 * @return {number}
 */
const numOfUnplacedFruits = function (fruits, baskets) {
  const st = new SegmentTree(baskets);
  let result = 0;

  for (const quantity of fruits) {
    const index = st.query(quantity);

    if (index === -1) {
      result += 1;
    } else {
      st.update(index, 0);
    }
  }

  return result;
};

class SegmentTree {
  constructor(nums) {
    this.n = nums.length;
    this.tree = Array.from({ length: this.n * 4 }, () => 0);
    this.build(nums, 0, 0, this.n - 1);
  }

  build(nums, index, left, right) {
    if (left === right) {
      this.tree[index] = nums[left];
      return;
    }
    const mid = Math.floor((left + right) / 2);

    this.build(nums, index * 2 + 1, left, mid);
    this.build(nums, index * 2 + 2, mid + 1, right);
    this.merge(index);
  }

  merge(index) {
    const a = this.tree[index * 2 + 1];
    const b = this.tree[index * 2 + 2];

    this.tree[index] = Math.max(a, b);
  }

  update(index, val) {
    this.#update(0, 0, this.n - 1, index, val);
  }

  #update(index, left, right, target, val) {
    if (left === right) {
      this.tree[index] = val;
      return;
    }
    const mid = Math.floor((left + right) / 2);

    if (mid >= target) {
      this.#update(index * 2 + 1, left, mid, target, val);
    } else {
      this.#update(index * 2 + 2, mid + 1, right, target, val);
    }

    this.merge(index);
  }

  query(target) {
    return this.#query(0, 0, this.n - 1, target);
  }

  #query(index, left, right, target) {
    if (this.tree[index] < target) return -1;
    if (left === right) return left;
    const mid = Math.floor((left + right) / 2);

    if (this.tree[index * 2 + 1] >= target) {
      return this.#query(index * 2 + 1, left, mid, target);
    } else {
      return this.#query(index * 2 + 2, mid + 1, right, target);
    }
  }
}