thảo luận Leetcode mỗi ngày

class Solution {
    public int maxTwoEvents(int[][] events) {
        int rs = 0, n = events.length;
        Arrays.sort(events, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        int sufM[] = new int[n], j = n - 1; sufM[j] = events[j][2];
        while (j-- > 0) sufM[j] = Math.max(sufM[j + 1], events[j][2]);
        for (int i = 0; i < n; i++) {
            int v = events[i][2], e = events[i][1];
            int bisectIdx = bS(0, n, m -> events[m][0] > e);
            if (bisectIdx < n) v += sufM[bisectIdx];
            rs = Math.max(rs, v);
        }
        return rs;
    }

    static int bS(int l, int r, Predicate<Integer> p) {
        while (l < r) { int m = l + r >>> 1; if (p.test(m)) r = m; else l = m + 1; } return l;
    }
}

var maxTwoEvents = function (events) {
    const q = new MinPriorityQueue();
    let ans = 0, max = 0;
    events.sort((u, v) => u[0] - v[0]);
    for (const [s, e, v] of events) {
        while (!q.isEmpty() && q.front().priority < s) {
            max = Math.max(max, q.dequeue().element);
        }
        ans = Math.max(ans, max +  v);
        q.enqueue(v, e);
    }
    return ans;
};

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        events.sort()
        heap = []
        ans, max_before_curr = 0, 0
        
        for s, e, v in events:
            while heap and heap[0][0] < s:
                max_before_curr = max(max_before_curr, heappop(heap)[1])

            ans = max(ans, max_before_curr + v)
            heappush(heap, (e, v))

        return ans

class Solution {
    public int maxTwoEvents(int[][] events) {
        int ans = 0;
        int n = events.length;
        Arrays.sort(events,(a,b)->{
            return a[0]-b[0];
        });
        int s = events[n-1][0];
        int max = events[n-1][2];
        Stack<int[]> st = new Stack<>();
        for(int i =n-1; i>=0;i--){
            while(i>=0 && events[i][0]==s){
                max = Math.max(max,events[i][2]) ;
                i--;
            }
            st.add(new int[]{s,max});
            if(i>=0){
                s=events[i][0];
                max = Math.max(max,events[i][2]);
            }
                
        }
        int[][] right_max = new int[st.size()][2];
        int size=0;
        while(!st.isEmpty()){
            int[] pair = st.pop();
            right_max[size][0]=pair[0];
            right_max[size][1]=pair[1];
            size++;
        }

        for(int i =0 ;i <n;i++){
            int val = events[i][2];
            int next = find_next_event(right_max,events[i][1]+1);
            if(next!=-1){
                val+=right_max[next][1];
            }
            ans=Math.max(ans, val);
        }
        return ans;
    }
    public int find_next_event(int[][] right_max, int start_time){
        int ans=-1;
        int l = 0;
        int r = right_max.length-1;
        while(l<=r){
            int mid = l+(r-l)/2;
            if(right_max[mid][0]>=start_time){
                ans = mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        return ans;
    }
}

class Solution {
    public int maxTwoEvents(int[][] events) {
        Arrays.sort(events, (a,b)->a[0]-b[0]);
        int n = events.length;
        int[] suffixMax = new int[n];
        suffixMax[n-1] = events[n-1][2];
        int res = 0;
        int index = 0;
        for(int i = n-2;i>=0;i--)
            suffixMax[i] = Math.max(suffixMax[i+1],events[i][2]);

        for(int[] ev: events){
            int end = ev[1];
            int sumIndex = binarySearch(events,index,end,n);
            if(sumIndex==n)
                res=Math.max(res,ev[2]);
            else
                res = Math.max(res, ev[2]+suffixMax[sumIndex]);
        }
        return res;
    }

    public int binarySearch(int[][] events, int index, int target, int r){
        int l = index;
        while(l<r){
            int mid = l+(r-l)/2;
            if(events[mid][0]>target)
                r = mid;
            else
                l = mid+1;
        }
        return l;
    }
}

class Solution:
    def maxTwoEvents(self, events):
        ev = sorted([e, v] for s, e, v in events)
        dp = list(accumulate((v for _, v in ev), func=max, initial=0))
        return max(dp[bisect_right(ev, [s, 0])] + v for s, _, v in events)

class Solution {
    fun maxTwoEvents(events: Array<IntArray>): Int {
        events.sortBy { it[1] }
        var ans = 0
        val maxEvent = IntArray(events.size)
        for (i in events.indices) {
            maxEvent[i] = maxOf(events[i][2], maxEvent.getOrElse(i - 1) { 0 })
        }
        events.forEachIndexed { index, event ->
            val (start, _, value) = event
            val idx = find(events, start, index - 1)
            val max = idx?.let { maxEvent[idx] + value } ?: value
            ans = maxOf(ans, max)
        }
        return ans
    }

    private fun find(events: Array<IntArray>, start: Int, i: Int): Int? {
        var s = 0
        var e = i
        var idx: Int? = null
        while (s <= e) {
            val m = s + (e - s) / 2
            if (events[m][1] < start) {
                idx = m
                s = m + 1
            } else {
                e = m - 1
            }
        }
        return idx
    }
}

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        # sort by end time
        ev = sorted([e, v] for s, e, v in events)

        # dp[i] = max value of first i events in ev
        dp = [0] * (len(events) + 1)
        curMax = 0
        for i in range(len(ev)):
            curMax = max(curMax, ev[i][1])
            dp[i+1] = curMax
        
        res = 0
        for s, e, v in events:
            # find number of non-overlapping earlier events in ev
            idx = bisect.bisect_right(ev, [s, 0])
            res = max(res, dp[idx] + v)

        return res

class Solution {
  public:
    int maxTwoEvents(vector<vector<int>> &events) {
        sort(begin(events), end(events), [](auto const &a, auto const &b) { return a[0] < b[0]; });
        int res = 0, n = events.size();
        vector<int> table(n + 1, 0);
        table[n - 1] = events[n - 1][2];
        for (int i = n - 2; i >= 0; --i)
            table[i] = max(table[i + 1], events[i][2]);
        for (int i = 0; i < n; ++i) {
            auto j = distance(begin(events), upper_bound(begin(events) + i, end(events), events[i][1],
                                                         [](int v, auto const &e) { return v < e[0]; }));
            res = max(res, events[i][2] + table[j]);
        }
        return res;
    }
};

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        events.sort()
        n = len(events)
        starts = [e[0] for e in events]
        @cache
        def dfs(i, is_first):
            if i == n:
                return 0
            if is_first:
                return max(dfs(i + 1, is_first), events[i][2] + dfs(bisect_right(starts, events[i][1]), False))
            return max(events[i][2], dfs(i + 1, False))

        return dfs(0, True)

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        n = len(nums)
        prefixSum = [0]*n
        for i in range(1, n):
            if nums[i]%2 != nums[i - 1]%2:
                prefixSum[i] = 1 + prefixSum[i - 1]
            else:
                prefixSum[i] = prefixSum[i - 1]

        ans = []
        for left, right in queries:
            if prefixSum[right] - prefixSum[left] == right - left:
                ans.append(True)
            else:
                ans.append(False)

        return ans

var isArraySpecial = function (nums, queries) {
    for (let i = 0; i < nums.length - 1; i++) {
        nums[i] = (1 ^ (nums[i] & 1) ^ (nums[i + 1] & 1)) + (i > 0 ? nums[i - 1] : 0);
    }
    nums.pop();
    return queries.map(([l, r]) => {
        if (l === r) {
            return true;
        }
        return !(nums[r - 1] - (l > 0 ? nums[l - 1] : 0));
    });
};

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        invalid = []
        for i in range(len(nums)-1):
            if (nums[i+1] - nums[i]) % 2 == 0:
                invalid.append(i)
      
        res = []
        for fr, to in queries:
            if fr == to:
                res.append(True)
                continue
            to -= 1
            idxFrom = bisect.bisect_left(invalid, fr)
            idxTo = bisect.bisect_left(invalid, to)
            res.append(idxFrom == idxTo and \
                (idxTo == len(invalid) or to != invalid[idxTo]))

        return res

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        # dp[i] = number of invalid adjacent pairs up to index i
        dp = [0] * len(nums)
        for i in range(1, len(nums)):
            if (nums[i] - nums[i-1]) % 2 == 0:
                dp[i] = dp[i-1] + 1
            else:
                dp[i] = dp[i-1]

        res = []
        for fr, to in queries:
            numInvalid = dp[to] - dp[fr]
            res.append(numInvalid == 0)
        return res

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        n = len(nums)
        prefix = [0] * n
        for i in range(n - 1):
            prefix[i+1] += 1 - (nums[i] & 1 == nums[i+1] & 1) + prefix[i]
        
        result = [True if prefix[t] - prefix[f] == t - f else False for f, t in queries]
        return result