leetcode-daily/Aug/06_Fruits_Into_Baskets_III.cpp at master · abhishekpaturkar/leetcode-daily · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
// 3479. Fruits Into Baskets III

// 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'

class Solution
{
    int n;
    vector<int> seg;
    void Update(int p)
    {
        seg[p] = max(seg[p << 1], seg[p << 1 | 1]);
    }

    void Build(int p, int l, int r, vector<int> &baskets)
    {
        if (l == r)
        {
            seg[p] = baskets[l];
            return;
        }
        int mid = (l + r) >> 1;
        Build(p << 1, l, mid, baskets);
        Build(p << 1 | 1, mid + 1, r, baskets);
        Update(p);
    }
    void Assign(int x, int v, int p, int l, int r)
    {
        if (x < l || x > r)
        {
            return;
        }
        if (l == r)
        {
            seg[p] = v;
            return;
        }
        int mid = (l + r) >> 1;
        Assign(x, v, p << 1, l, mid);
        Assign(x, v, p << 1 | 1, mid + 1, r);
        Update(p);
    }
    int FirstLarger(int v, int p, int l, int r)
    {
        if (seg[p] < v)
        {
            return r + 1;
        }
        if (l == r)
        {
            return r;
        }
        int mid = (l + r) >> 1;
        int lf = FirstLarger(v, p << 1, l, mid);
        if (lf <= mid)
        {
            return lf;
        }
        return FirstLarger(v, p << 1 | 1, mid + 1, r);
    }

public:
    int numOfUnplacedFruits(vector<int> &fruits, vector<int> &baskets)
    {
        n = fruits.size();
        seg.assign(4 * n + 1, 0);
        Build(1, 0, n - 1, baskets);
        int res = 0;
        for (const auto &x : fruits)
        {
            int pos = FirstLarger(x, 1, 0, n - 1);
            if (pos == n)
            {
                res++;
            }
            else
            {
                Assign(pos, 0, 1, 0, n - 1);
            }
        }
        return res;
    }
};