Chương trình tìm số chân tối thiểu cần thiết để treo tất cả các biểu ngữ trong C ++

Giả sử chúng ta có một danh sách các khoảng có dạng [bắt đầu, kết thúc], đây là đại diện cho điểm bắt đầu và điểm kết thúc của biểu ngữ mà chúng ta muốn treo. Cần có ít nhất một chốt để treo băng rôn và một chốt có thể treo nhiều băng rôn. Chúng tôi phải tìm số lượng đinh ghim nhỏ nhất cần thiết để treo tất cả các biểu ngữ.

Vì vậy, nếu đầu vào giống như khoảng =[[2, 5], [5, 6], [8, 10], [10, 13]], thì đầu ra sẽ là 2, vì chúng ta có thể đặt hai chân ở vị trí 5 và 10 để treo tất cả các biểu ngữ.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sắp xếp mảng v dựa trên giá trị cuối của các khoảng
• ret:=0
• cuối cùng:=-inf
• cho mỗi mục, nó trong v -
  • if last> =start of it, then -
    • Bỏ qua phần sau, chuyển sang phần lặp tiếp theo
  • (tăng ret thêm 1)
  • cuối cùng:=kết thúc nó
• trả lời lại

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   static bool cmp(vector<int>& a, vector<int>& b) {
      return a.back() < b.back();
   }
   int solve(vector<vector<int>>& v) {
      sort(v.begin(), v.end(), cmp);
      int ret = 0;
      int last = -1e8;
      for (auto& it : v) {
         if (last >= it[0]) {
            continue;
         }
         ret++;
         last = it[1];
      }
      return ret;
   }
};
int solve(vector<vector<int>>& intervals) {
   return (new Solution())->solve(intervals);
}
int main(){
   vector<vector<int>> v = {{2, 5},{5, 6},{8, 10},{10, 13}};
   cout << solve(v);
}

Đầu vào

{{2, 5},{5, 6},{8, 10},{10, 13}}

Đầu ra

2