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

var findMinArrowShots = function (points) {
    let ans = 1
    points.sort((a, b) => (a[0] - b[0]))
    let top = points[0][1]
    for (let i = 1; i < points.length; i++) {
        if (top < points[i][0]) {
            top = points[i][1]
            ans++
        }
        else if (top > points[i][1]) top = points[i][1]
    }
    return ans
};

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        sorted_points = sorted(points, key=lambda x: x[1])
        count = 0;
        shoot_point = float('-inf')
        for point in sorted_points:
            if point[0] > shoot_point:
                shoot_point = point[1]
                count += 1
        return count

func findMinArrowShots(points [][]int) int {
    sort.Slice(points, func(i, j int) bool {
        if points[i][0] == points[j][0] {
            return points[i][1] < points[j][1]
        }
        return points[i][0] < points[j][0]
    })
    ans := make([][]int, 0)
    for _, point := range points {
        if len(ans) != 0 {
            point2 := ans[len(ans)-1]
            if point2[1] < point[0] {
                ans = append(ans, point)
            } else {
                point2[0] = int(math.Max(float64(point2[0]), float64(point[0])))
                point2[1] = int(math.Min(float64(point2[1]), float64(point[1])))
            }
        } else {
            ans = append(ans, point)
        }
    }
    return len(ans)
}

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, Comparator.comparing(a -> a[0]));
        int ans = 0;
        int[] curJoin = points[0];

        for (int i = 1; i < points.length; i++) {
            if (points[i][0] <= curJoin[1]) {
                curJoin[0] = points[i][0];
                curJoin[1] = Math.min(points[i][1], curJoin[1]);
                continue;
            } else {
                curJoin = points[i];
                ans++;
            }
        }

        return ans + 1;
    }
}

    public int FindMinArrowShots(int[][] points) {
        points = points.OrderBy(p => p[0]).ToArray();
        int cnt = 0;
        int lastEnd = int.MaxValue;
        foreach (var point in points)
        {
            if (point[0] <= lastEnd)
            {
                lastEnd = Math.Min(lastEnd, point[1]);
            }
            else
            {
                cnt++;
                lastEnd = point[1];
            }
        }
        return cnt + 1;
    }

var findMinArrowShots = function (points) {
  points.sort((pointX, pointY) => pointX[0] - pointY[0]);

  let count = 1,
    topBorder = points[0][1];

  for (let i = 1; i < points.length; i++) {
    if (topBorder < points[i][0]) {
      topBorder = points[i][1];
      count++;
    } else if (topBorder > points[i][1]) topBorder = points[i][1];
  }

  return count;
};

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.size() == 1)
            return 1;

        sort(points.begin(), points.end(), [](auto a, auto b){ return a[0] < b[0];});
        deque<vector<int>> stack(points.begin(), points.end());

        int count = 1;
        while(stack.size() > 1) {
            auto first = stack.front(); stack.pop_front();
            auto second = stack.front();
            if (first[1] >= second[0]) {
                second[1] = min(first[1], second[1]);
                stack.pop_front();
                stack.push_front(second);
            } else {
                count++;
            }
        }
        return count;
    }
};

function findMinArrowShots(points: number[][]): number {

    points.sort((a,b) => a[1] === b[1] ? a[0] - b[0] : a[1] - b[1])

    let count = 1;

    let currentArrow = points[0][1];

    let i = 1;

 

    while (i < points.length) {

        const [start, end] = points;

        const isHit = currentArrow >= start && currentArrow <= end;

        if (!isHit) {

            count++

            currentArrow = points[1]

        }

        i++

    }

    return count
};

class Solution {
public:
    bool mergedData(vector<int> &v1, vector<int> &v2)
    {
        if(v1[1] < v2[0])
        {
            return false;
        }
        v2[1] = min(v1[1], v2[1]);
        return true;
    }
    static bool softV(vector<int> &v1, vector<int> &v2)
    {
        return v1[0] < v2[0];
    }
    int findMinArrowShots(vector<vector<int>>& points)
    {
      auto count = 1;
      sort(points.begin(), points.end(), softV);
      for(auto i=0;i<points.size()-1;++i)
      {
          if (!mergedData(points[i],points[i+1]))
          {
              count++;
          }
      }
      return count;
    }
};

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        def compFunc(x):
            return x[0] , x[1]
        points.sort(key=compFunc)
        n = len(points)
        res = 1
        [l , r] = points[0]
        for i in range(1 , n):
            curPoints = points[i]
            if l > curPoints[1] or r < curPoints[0]:
                res += 1
                l = curPoints[0]
                r = curPoints[1]
                continue

            if curPoints[0] > l : l = curPoints[0]
            if curPoints[1] < r : r = curPoints[1]
            
        return res

pub fn find_min_arrow_shots(mut points: Vec<Vec<i32>>) -> i32 {
    points.sort_unstable();
    let mut count = 0;
    let mut i = 0;
    let n = points.len();
    while i < n {
        // Shoot down current balloon
        let (mut start, mut end) = (points[i][0], points[i][1]);
        count += 1;
        i += 1;
        // If other balloons intersect with current one, they will be bursted as well.
        // However, the more balloons we want to burst in a single shot, the narrower
        // range of `x` we can choose
        while i < n && start <= points[i][0] && points[i][0] <= end {
            start = points[i][0];
            end = end.min(points[i][1]);
            i += 1;
        }
    }
    count
}

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        frequency = defaultdict(int)
        maxFrequency = 0
        maxCount = 0
        for task in tasks:
            frequency[task] += 1
            if frequency[task] > maxFrequency:
                maxFrequency = frequency[task]
                maxCount = 1
            elif frequency[task] == maxFrequency:
                maxCount += 1

        return max((maxFrequency - 1)*n + maxFrequency + maxCount - 1, len(tasks))

/**
 * @param {character[]} tasks
 * @param {number} n
 * @return {number}
 */
var leastInterval = function (tasks, n) {
    const taskCounts = new Array(26).fill(0);
   
    for (const task of tasks) {
        const index = task.charCodeAt(0) - 'A'.charCodeAt(0);
        taskCounts[index]++;
    }
   
    taskCounts.sort((a, b) => b - a);
   
    let maxCount = taskCounts[0] - 1;
    let idleSlots = maxCount * n;
   
    for (let i = 1; i < taskCounts.length; i++) {
        idleSlots -= Math.min(taskCounts[i], maxCount);
    }
   
    idleSlots = Math.max(0, idleSlots); // idleSlots could be negative if there are no idle intervals needed
   
    return tasks.length + idleSlots;
};

function leastInterval(tasks: string[], n: number): number {
    const arr = new Array(26).fill(0);
    for (const task of tasks) arr[task.charCodeAt(0) - 'A'.charCodeAt(0)]++;
    arr.sort((a,b) => a - b);
    let max = arr[25] - 1, k = max * n;
    for (let i = 24; i >= 0 && arr[i] > 0; i--) k-= Math.min(max, arr[i])
    return k > 0 ? k + tasks.length : tasks.length;
};

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        array<int, 26> arr = {0};
        for (auto task : tasks) {
            arr[task - 'A']++;
        }
        priority_queue<pair<int, int>> q;
        for (auto x : arr) {
            if (x > 0) q.emplace(-1, x);
        }
        int time = 0;
        while(!q.empty()) {
            auto [time_top, num_top] = q.top();
            q.pop();
            time = max(time + 1, time_top*-1);
            if (num_top > 1) q.emplace(time_top - n - 1, num_top - 1);
        }
        return time;
    }
};

public class Solution
{
    public int LeastInterval(char[] tasks, int n)
    {
        int[] map = new int[26];
        for (int i = 0; i < tasks.Length; i++)
        {
            map[tasks[i] - 'A']++;
        }
        Array.Sort(map, (a, b) => b - a);

        int chunk = map[0] - 1;
        int idle = chunk * n;
        for (int i = 1; i < map.Length; i++)
        {
            idle -= Math.Min(chunk, map[i]);
        }

        return idle < 0 ? tasks.Length : tasks.Length + idle;
    }
}

class Solution {
    class Pair {
       char key;
       int count;
       Pair(char key, int count){
        this.key = key;
        this.count = count;
       }
    }
    public int leastInterval(char[] tasks, int n) {
        Map<Character,Pair> countTask = new HashMap<>();
        int ans = 0;
        for(Character task : tasks){
            Pair temp = countTask.getOrDefault(task, new Pair(task,0));
            temp.count = temp.count + 1;
            countTask.put(task,temp);
        }
        PriorityQueue<Pair> queue = new PriorityQueue<>((a, b) -> b.count - a.count);
        while(countTask.size() != 0){
            int index = 0;
            for(Character key : countTask.keySet()){
                queue.offer(countTask.get(key));
      
            }
            while(!queue.isEmpty() && index <= n){
                Pair temp = queue.poll();
                int count = countTask.get(temp.key).count;
                count -= 1;
                countTask.get(temp.key).count = count;
                if(count == 0){
                    countTask.remove(temp.key);
                }
                ans++;
                index++;
            }
            queue.clear();
            if(n-index >= 0 &&countTask.size()!=0)
                ans += n-index +1;
        }
        return ans;
    }
}

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char,int> m; // last pos of c
        vector<int> q;
        for (char &c : tasks) {
            int t = m[c]+n+1;
            q.push_back(t);
            m[c] = t;
        }
        sort(q.begin(),q.end());
        int ans = 0;
        for (int &t : q) ans = max(ans+1,t);
        return ans-n;
    }
};

fun leastInterval(tasks: CharArray, n: Int): Int {
        val count = IntArray(26)
        for (task in tasks) {
            count[task - 'A']++
        }
        val maxCount = count.max()
        val time = (maxCount - 1) * (n + 1) + count.count { it == maxCount }

        return maxOf(tasks.size, time)
    }