LeetCode - 3479. Fruits Into Baskets III

Medium

這題 Segment Tree 竟然才 Medium，太狠了

3479. Fruits Into Baskets III

Problem

You are given two arrays: fruits and baskets, both of length n.
fruits[i] represents the number of fruits of type i, and baskets[j] is the capacity of basket j.

Starting from the left, you place fruits into baskets according to the following rules:

• Each fruit type must be placed into the leftmost unused basket whose capacity is ≥ the number of fruits.
• Each basket can hold only one type of fruit.
• If a fruit type cannot be placed in any basket, it is considered unplaced.

Return the number of fruit types that cannot be placed in any basket.

Example 1

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

Explanation:

• Fruit 4 → goes into basket[1] = 5
• Fruit 2 → goes into basket[0] = 3
• Fruit 5 → cannot be placed

---

Example 2

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

Explanation:

• 3 → basket[0] = 6
• 6 → basket[2] = 7
• 1 → basket[1] = 4

All fruits are placed successfully.

---

Constraints

• n == fruits.length == baskets.length
• 1 <= n <= 10^5
• 1 <= fruits[i], baskets[i] <= 10^9

---

解題思路

這題其實就是 「每種水果都想找一個最左邊還可以放得下的籃子」
用暴力一個一個檢查的話，n 上限 10^5，必 TLE

所以這題要用 Segment Tree + Binary Search

1. Initial Segment Tree

   • 樹上儲存每個區間裡能放進的最大籃容量 max
   • 建 segment tree 的空間大概會是 input 長度的 4 倍，所以設 segTree_size = 4 * n + 5

2. Build Segment Tree
   build_segment_tree(now, left, right)：

   • left == right → 葉節點就是 baskets[left]
   • mid 拆兩邊建，最後 parent = max(left child, right child)

3. Search leftmost_basket
   用 Binary Search + Segment Tree：

   • 對每個 fruit i，設定 left = 0, right = n - 1, leftmost_basket = -1
   • mid = (left+right)/2，如果 query (0 ~ mid) 的區間 max ≥ fruit，就代表左邊有人能放，那就把 leftmost 定 mid，但繼續往左找；不然 left = mid+1
   • 對這段 range 用 Segment Tree 做 query，複雜度是 O(log n)

4. update used basket in Segment Tree
   如果找到就 update_segment_tree(now, left, right, position, INT_MIN)，意思就是把這格設超小，之後查不到它，像被用過了

5. Time & Space Complexity

   • Time：建樹 O(n)，每次 Binary Search O(log n) + 每次查詢/更新 segtree O(log n)，總共 fruits 有 n 顆 → O(n log n)
   • Space：Segment Tree 用 O(n) 空間

因為註解是邊解邊寫的，我覺得我註解寫的比較容易理解，也可以直接看註解去理解這題 XD

---

C++ Solution

class Solution {
private:
    const int segTree_size = 400005; // 因為 segTree 的空間複雜度大約會是 input 範圍上限的四倍
    vector<int> baskets;
    vector<int> segTree;
public:
    void build_segment_tree(int now, int left, int right){
        if(left == right){
            segTree[now] = baskets[left];
            return;
        }
        int mid = (left + right) >> 1;
        build_segment_tree(now << 1, left, mid);
        build_segment_tree(now << 1 | 1, mid + 1, right);
        segTree[now] = max(segTree[now << 1], segTree[now << 1 | 1]); // now << 1 | 1 = (now * 2) + 1
    }
    int query_leftmost_interval(int now, int left, int right, int query_left, int query_right){
        if(query_left > right || query_right < left) return INT_MIN; // 設一個超小值，相當於此 basket 已被使用
        if(query_left <= left && query_right >= right) return segTree[now]; // 一直去調整 left 和 right 的範圍直到完全被 include 在 query_left ~ query_right 之間
        int mid = (left + right) >> 1;
        return max(query_leftmost_interval(now << 1, left, mid, query_left, query_right), query_leftmost_interval(now << 1 | 1, mid + 1, right, query_left, query_right));
    }
    void update_segment_tree(int now, int left, int right, int position, int value){
        if(left == right){
            segTree[now] = value; // 查找到這個 position(leftmost_basket idx) 區間，把他值設成超小值，更新此 basket 已被使用
            return;
        }
        int mid = (left + right) >> 1;
        if(position <= mid) update_segment_tree(now << 1, left, mid, position, value); // 我覺得要判斷這個 now << 1 位址是 seg tree 最難的地方，或是這就是公式硬記(?
        else update_segment_tree(now << 1 | 1, mid+1, right, position, value);
        segTree[now] = max(segTree[now << 1], segTree[now << 1 | 1]);
    }

    Solution() : segTree(segTree_size) {} // 偶爾複習一下 constructor 寫法唄
    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        this->baskets = baskets; // 物件導向，this->指的是「class 裡的 baskets」，也就是賦予 class 內部的 baskets 物件來自外部的 baskets 物件的值
        if(baskets.size() == 0) return fruits.size();

        build_segment_tree(1, 0, baskets.size() - 1);

        int ans = 0;
        for(int i = 0; i < fruits.size(); ++i){ // 遍歷每個 fruits 有沒有機會有 leftmost_basket
            int left = 0, right = baskets.size() - 1, leftmost_basket = -1;
            while(left <= right){
                int mid = (left + right) >> 1;
                // 查找 0~mid 之間是否有任何 basket 放得下 fruit 有的話就要排除 (區間 segTree 裡面存的是該區間的最大值)
                if(query_leftmost_interval(1, 0, baskets.size() - 1, 0, mid) >= fruits[i]){ 
                    leftmost_basket = mid; // 因為現在是 0~mid 有 leftmost，所以先把 leftmost 設成 mid，若之後試 0~(mid-1) 沒有符合的 basket，代表 leftmost 就是 mid
                    right = mid - 1;
                }
                else left = mid + 1; // 0~mid 之間沒有放得下的 basket，因此 left 往右
            }
            if(leftmost_basket != -1 && baskets[leftmost_basket] >= fruits[i]){ // 如果真找到這個符合條件的 leftmost_basket
                update_segment_tree(1, 0, baskets.size() - 1, leftmost_basket, INT_MIN);
            }
            else ans++; // 這水果沒地方放啊，ans++ !
        }
        return ans;
    }
};