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

/**
 * @param {number[]} nums
 * @param {number} maxOperations
 * @return {number}
 */
var minimumSize = function (nums, maxOperations) {
    const go = cap => {
        let ops = 0;
        for (const n of nums) {
            ops += Math.ceil(n / cap) - 1;
            if (ops > maxOperations) {
                return false;
            }
        }
        return true;
    };
    let l = 1, h = _.max(nums) + 1;
    while (l < h) {
        const m = (l + h) >> 1;
        if (go(m)) {
            h = m;
        } else {
            l = m + 1;
        }
    }
    return l;
};

function minimumSize(nums: number[], maxOperations: number): number {
    let l = 1
    let r = Math.max(...nums)

    while (l < r) {
        let mid = Math.floor((l + r) / 2)
        let curOpe = 0
        for (const num of nums) {
            if (num > mid) {
                curOpe += Math.ceil(num / mid) - 1
            }
        }

        if (curOpe <= maxOperations) {
            r = mid
        } else {
            l = mid + 1
        }
    }

    return r
};

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        def f(m):
            op = 0

            for num in nums:
                if num > m:
                    d = num // m - (num % m == 0)
                    op += d
                    if op > maxOperations:
                        return False
           
            return True
               
        l = 1
        r = max(nums)

        while l < r:
            m = l + (r - l)//2
            if f(m):
                r = m
            else:
                l = m + 1
       
        return l

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        l, r = 1, max(nums)
        while l < r:
            m = l + (r - l)//2
            if sum(ceil(n / m ) - 1 for n in nums) <= maxOperations: r = m
            else: l = m + 1
        return l

class Solution {
    public int minimumSize(int[] nums, int maxOperations) {
        Arrays.sort(nums);
        int r = 1;
        int l = 1;
        for (int num : nums) {
            r = Math.max(r, num);
        }
        int ans =r;
        while(l<=r){
            int mid =l+(r-l)/2;
            if(canDivide(mid, nums, maxOperations)){
                ans = mid;
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        return ans;
    }
    public boolean canDivide(int max, int[] nums, int o){
        for(int i = nums.length-1;i>=0;i--){
            int balls =nums[i];
            if(balls<=max&& o>=0) return true;
            else{
                o-=((balls+max-1)/max-1);
            }
            if(o<0) return false;
        }
        return true;
    }
}

var minimumSize = function(nums, maxOperations) {
    const max = Math.max(...nums);
    let left = 1;
    let right = max;
    const isValidMinSize = (minSize) => {
        let operationsCount = 0;
        for(const num of nums){
            operationsCount += (Math.ceil(num / minSize) - 1);
            if(operationsCount > maxOperations) return false;
        }
        return true;
    }
    while(left < right){
        const mid = left + Math.floor((right - left) / 2);
        if(isValidMinSize(mid)){
            right = mid;
        }
        else left = mid + 1;
    }
    return left;
};

class Solution {
    fun minimumSize(nums: IntArray, maxOperations: Int): Int {
        nums.sort()
        var ans = Int.MAX_VALUE
        var min = 1
        var max = nums.last()
        while (min <= max) {
            val mid = min + (max - min) / 2
            var count = 0
            for (num in nums) {
                count += (num - 1) / mid
            }
            if (count <= maxOperations) {
                ans = minOf(ans, mid)
                max = mid - 1
            } else {
                min = mid + 1
            }
        }
        return ans
    }
}

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        maxBags = len(nums) + maxOperations
        l, r = 1, max(nums)
        res = r
        while l <= r:
            m = (l + r) // 2
            minBags = 0
            for sz in nums:
                minBags += math.ceil(sz / m) if sz > m else 1
            if minBags > maxBags:
                l = m + 1
            else:
                r = m - 1
                res = min(res, m)
        return res

class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        int l = 1;
        int r = 1e9;
        int res;
        while(l <= r){
            int mid = (l + r) / 2;
           
            int count = 0;
            for(int i=0; i<nums.size(); i++){
                count += ceil(nums[i] /(double) mid) - 1;
            }
            if(count > maxOperations){
                l = mid + 1;
            }
            else {
                res = mid;
                r = mid - 1;
            }
        }
        return res;
    }
};

public class Solution {
    public bool IsValid(int[] nums, int result, int maxOperations)
    {
        int temp = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] > result)
            {
                temp += (int)Math.Ceiling(nums[i] * 1.0 / result) - 1;
            }
        }
        return temp <= maxOperations;
    }

    public int MinimumSize(int[] nums, int maxOperations) {
        int left = 0;
        int right = nums.Max();
        int mid = 0;
        while (left < right-1)
        {
            mid = left + (right - left) / 2;
            if (IsValid(nums, mid, maxOperations))
                right = mid;
            else
                left = mid;
        }
        return right;
    }
}

func minimumSize(nums []int, maxOperations int) int {
    left, right := 1, -1

    for _, num := range nums {
        right = max(right, num)
    }

    for ;left < right; {
        mid := left + (right - left) / 2

        op := 0
        for _, num := range nums {
            op += (num - 1) / mid
        }

        if op <= maxOperations {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return right
}

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        events.sort(key=lambda x: x[1], reverse=True)
        q, maxCurr, result = [], 0, 0

        for start, end, value in events:
            while q and -q[0][0] > end:
                maxCurr = max(maxCurr, q[0][1])
                heapq.heappop(q)
            
            result = max(result, maxCurr + value)
            heapq.heappush(q, (-start, value))
        return result

function maxTwoEvents(events: number[][]): number {
    let ev = []

    for (const event of events) {
        ev.push([event[0], 1, event[2]])
        ev.push([event[1] + 1, -1, event[2]])
    }

    // Sort by the time, if equal sort by type (1 or -1)
    ev.sort((a, b) => a[0] - b[0] || a[1] - b[1])

    let maxp = 0
    let best = 0

    for (let e of ev) {
        const [x, t, v] = e

        if (t === 1) {
            best = Math.max(best, maxp + v)
        }

        if (t === -1) {
            maxp = Math.max(maxp, v)
        }
    }

    return best

};

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        events = sorted(events)
        n = len(events)
        dp = [(-1, -1)]*n
        dp[-1] = (events[-1][0], events[-1][2])
        for i in range(n - 2, -1, -1):
            dp[i] = (events[i][0], max(events[i][2], dp[i + 1][1]))

        def bisearch(endTime):
            left = 0
            right = n - 1
            ans = -1
            while left <= right:
                mid = left + (right - left)//2
                if dp[mid][0] > endTime:
                    ans = mid
                    right = mid - 1
                else:
                    left = mid + 1

            return 0 if ans == -1 else dp[ans][1]

        ans = -inf
        for i in range(n):
            ans = max(ans, events[i][2] + bisearch(events[i][1]))

        return ans

class Solution {
    public int maxTwoEvents(int[][] events) {
        Queue<Event> pq = new PriorityQueue<>((a,b) -> a.endTime - b.endTime);
        Arrays.sort(events, (a,b) -> a[0] - b[0]);

        int maxSum = 0;
        int maxVal = 0;
        for(int i = 0;i<events.length;i++){
            while(!pq.isEmpty() && pq.peek().endTime < events[i][0]){
                maxVal = Math.max(maxVal,pq.peek().value);
                pq.poll();
            }
            maxSum = Math.max(maxSum, maxVal + events[i][2]);
            pq.add(new Event(events[i][0],events[i][1],events[i][2]));
        }

        return maxSum;
    }
}
public class Event{
    public int startTime;
    public int endTime;
    public int value;
    public Event(int startTime,int endTime,int value){
        this.startTime = startTime;
        this.endTime = endTime;
        this.value = value;
    }
}