3477. Fruits Into Baskets II

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 <= 100
• 1 <= fruits[i], baskets[i] <= 1000

 

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) {
    if (st.query(quantity) === -1) {
      result += 1;
    }
  }

  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, low, high) {
    if (low === high) {
      this.tree[index] = nums[low];
      return;
    }
    const mid = Math.floor((low + high) / 2);

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

  update(target, val) {
    this._update(0, 0, this.n - 1, target, val);
  }

  _update(index, low, high, target, val) {
    if (low === high) {
      this.tree[index] = val;
      return;
    }
    const mid = Math.floor((low + high) / 2);

    if (target <= mid) {
      this._update(index * 2 + 1, low, mid, target, val);
    } else {
      this._update(index * 2 + 2, mid + 1, high, target, val);
    }

    this.merge(index);
  }

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

  _query(index, low, high, target) {
    if (this.tree[index] < target) return -1;
    if (low === high) {
      this.update(low, -1);
      return low;
    }
    const mid = Math.floor((low + high) / 2);

    if (this.tree[index * 2 + 1] >= target) {
      return this._query(index * 2 + 1, low, mid, target);
    } else {
      return this._query(index * 2 + 2, mid + 1, high, target);
    }
  }

  merge(index) {
    this.tree[index] = Math.max(this.tree[index * 2 + 1], this.tree[index * 2 + 2]);
  }
}