2054. Two Best Non-Overlapping Events

難度: Medium

類型: Array, Binary Search, Dynamic Programming, Sorting,Heap (Priority Queue)

CPP程式下載: 2054.cpp

前情題要:

最多可以參加兩個時間不重疊的事件, 獲得事件的value相加, 求最大值。

You are given a 0-indexed 2D integer array of events where events[i] = [startTimei, endTimei, valuei]. The ith event starts at startTimei and ends at endTimei, and if you attend this event, you will receive a value of valuei. You can choose at most two non-overlapping events to attend such that the sum of their values is maximized.

Return this maximum sum.

Note that the start time and end time is inclusive: that is, you cannot attend two events where one of them starts and the other ends at the same time. More specifically, if you attend an event with end time t, the next event must start at or after t + 1.

 

Example 1:

Input: events = [[1,3,2],[4,5,2],[2,4,3]]
Output: 4
Explanation: Choose the green events, 0 and 1 for a sum of 2 + 2 = 4.

Example 2:

Input: events = [[1,3,2],[4,5,2],[1,5,5]]
Output: 5
Explanation: Choose event 2 for a sum of 5.

Example 3:

Input: events = [[1,5,3],[1,5,1],[6,6,5]]
Output: 8
Explanation: Choose events 0 and 2 for a sum of 3 + 5 = 8.

 

Constraints:

• 2 <= events.length <= 105
• events[i].length == 3
• 1 <= startTimei <= endTimei <= 109
• 1 <= valuei <= 106

思考方式:

1. 把array找開始時間排序

2. 只要與 left index 開始時間事件不重疊, 那所有後面(右邊)的開始事件都不回重疊。

3. 紀錄右邊所有事件的最大 value

4. 用 binary search 找不與目前event結束時間重疊的事件, 取最大 value 值。

複雜度思考:

Time Complexity: O( 2*N+log2(N) ) 

Space Complexity: O( x )

結果:

Runtime: 72 ms, Beats: 72.97%

Memory: 158.65 MB, Beats: 72.19%

All Submissions

Accepted

64 / 64 testcases passed

tendchen

submitted at Jun 09, 2025 11:09

Runtime

72ms

Beats72.97%

Analyze Complexity

Memory

158.65MB

Beats72.19%

Analyze Complexity

0.16% of solutions used 43 ms of runtime

C++程式碼:

class Solution {

public:

    int maxTwoEvents(vector<vector<int>>& events) {

        int i,left,right,mid,ans=0,non_overlap;

        int max_val=0;

        //cout<< events[0][2] << ' ' << events[1][2] << ' ' << events[2][2] << '\n';

        ranges::sort(events);

        //cout<< events[0][2] << ' ' << events[1][2] << ' ' << events[2][2]<< '\n';

        int n = events.size();

        //cout << "n=" << n << "\n";

       

        vector<int> f(n);

        for (i=n-1;i>0;i--)

        {

            if (max_val<events[i][2])

            {

                max_val=events[i][2];

            }

            f[i]=max_val;

            //f[i]=max(f[i+1],events[i][2]);

            //cout<<"f["<<i<<"]="<<f[i]<<endl;

        }

        for (i=0;i<n;i++)

        {

            left=i+1;

            right=n-1;

            if (i>0)

            {

                if ((events[i-1][1]<=events[i][1])&&(events[i-1][2]>=events[i][2])) continue;

            }

            non_overlap=0;

            do

            {

                mid=(left+right)>>1;

                //cout << "left=" << left << ",right=" << right << "\n";

                //printf("events[%d][1]=%d,events[%d][0]=%d\n",i,events[i][1],mid,events[mid][0]);

                if (events[i][1]<events[mid][0])

                {

                    right=mid;

                    non_overlap++;

                    //cout << "Non-Overlap++" <<"\n";

                }

                else

                {

                    left=mid+1;

                }

            } while ((left<right)||((non_overlap==0)&&(left==right)));

            //cout <<"left= " << left << " right=" << right <<"\n";

            //cout <<"non_overlap= " << non_overlap <<"\n";

            //cout <<"i= " << i <<"\n";

            //cout <<"events[i][2]="<<events[i][2]<<endl;

            if (non_overlap)

                ans = max(ans,(events[i][2]+f[left]));

            else

                ans = max(ans,events[i][2]);

            //cout <<"ans= " << ans << "\n";

        }

        return ans;

    }

};

1760. Minimum Limit of Balls in a Bag

 1760. Minimum Limit of Balls in a Bag

難度: Medium

類型: Array, Binary Search

CPP程式下載: 1760.cpp

前情題要:

第 i 個袋子裡有 nums[i] 個球, 有 MaxOperations 次可以把袋子分裝成兩袋的機會, 所有袋子裡最多的球數當作 cost, 那麼能夠達到最小的 cost 為何?

思考方式:

Binary Search, 每次把範圍縮一半, 直到找到最小值。

複雜度思考:

Time Complexity: O( log2(N) ) 

Space Complexity: O( x )

結果:

Runtime: 27 ms, Beats: 83.93%

Memory: 59.69 MB, Beats: 96.72%

2762. Continuous Subarrays

 2762. Continuous Subarrays

難度: Medium

類型: Array, Queue,Sliding Window, Heap (Priority Queue), Ordered Set, Monotonic Queue

CPP程式下載: 2762_1.cpp 2762_2.cpp

前情題要:

連續的子陣列。任意個子陣列裡的值相減必須小於等於2

思考方式:

1. 用 Sliding Window 的方式, 抓 high low index。

2. 解出來不難, 但要夠快, 能排名在前面不容易。

3. 2762_1.cpp, 用 multiset, 能自動排序且數值可以重複, 最右邊的最大值減掉最左邊的最小值, 就能判斷是否符合 substring 要相減 "<=2" 的條件。每次sliding window 的左邊 low index 移動前, 要先找到multiset中相同值並移除。這可以做到 230~240 ms 的速度, 約Beat 22~23%, 而且multiset存了太多數值, 空間約156MB, Beat 19%。

4. 2762_2.cpp, 相減要小於等於2, 所以取任一值當中心點, 其他的數字只可能在 -2~+2 的範圍, 所以只需要存五個值的出現次數 "freq_range[5]"。當移動sliding window 的左邊 low index 時, 根據 low index 位置數值和前次的 low index 數值的差, 來移動freq_range[5]; freq_range[2]永遠都是目前 low index那個值出現的次數。一直保留前次的high index, 並讓sliding window試著往右邊推進。因為只有存五個值的freq, 所以移動起來容易(運算少), 而且不須存大量的資料。在時間和空間上都有效率。不過就是程式比較繁瑣, 要考慮的 boundary condition 比較多。

複雜度思考:

Time Complexity: O( 2*N ) 

Space Complexity: O( 16*sizeof(int) + sizeof(long long) )

結果:

Runtime: 78 ms, Beats: 91.90%

Memory: 111.69 MB, Beats: 97.92%

790. Domino and Tromino Tiling

 790. Domino and Tromino Tiling

難度: Medium

類型: Dynamic Programming

CPP程式下載: 790.cpp

前情題要:

2*1 的骨牌, 與2*2缺一格的骨牌組合(可旋轉)。有多少種組合方式能得到一個2*n的長條形。(數字很大, 必須 modulo 10^9+7)

思考方式:

老實說, 這一題對我來說很難。而且我認為這題是數學題, 而不是 Dynamic Programming。如果想得到很棒的數學表示方式, 那就能用很精簡的程式算出答案。

1. 定義 F(N) 和 G(N)。F(N) 是組成2*N的長條形的可能組合個數。G(N)是組成2*N長條形卻缺了右下一格的組合個數。

2. F(N)=2*G(N-1)+F(N-2)+F(N-1) :

    (2-1) G(N-1), 右下缺一個的形狀, 配上左上缺一個的 Tromino tile。能構成 F(N)。

    (2-2) G(N-1), 右上缺一個的形狀, 配上左上缺一個的 Tromino tile。能構成 F(N)。

    (2-3) F(N-2), 配上兩個橫置並排 2*1 的骨牌, 能構成 F(N)

    (2-4) F(N-1), 配上一個 2*1 的骨牌, 能構成 F(N)

3. G(N)=G(N-1)+F(N-2) :

    (3-1) G(N-1) 缺右下的改成缺右上的, 個數一樣, 再搭配一個2*1的骨牌橫置擺在右上那一排, 就成了G(N)缺右下的。

    (3-2) F(N-2) 就是 2*(N-2) 的長條形配上一個2*2但右下缺一格的骨牌, 就成了G(N)。

複雜度思考:

Time Complexity: O( 2*N ) 

Space Complexity: O( x )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 8.33 MB, Beats: 8.94%