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;

    }

};