首页CodeForces - 1110D

CodeForces - 1110D

时间: 2025-06-29 12:06:26 浏览: 7

### CodeForces Problem 1110D Solution and Explanation The problem titled "Ehab Has a Lot of Work" requires participants to handle tasks represented as intervals on a timeline. Each task has a start time \( l_i \) and an end time \( r_i \). The goal is to determine whether it's possible to select at least one point within each interval such that all selected points are distinct. To solve this, consider using a greedy algorithm approach: #### Greedy Algorithm Approach A key observation lies in choosing the smallest endpoint available from unprocessed segments after sorting them by their endpoints. This ensures minimal overlap while maximizing coverage efficiency[^3]. ```cpp #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<pair<int,int>> v(n); set<int> s; for (auto &i : v){ cin >> i.first >> i.second; s.insert(i.second); // Inserting ending times into set. } sort(v.begin(),v.end()); bool flag=true; for(auto p:v){ auto pos=s.lower_bound(p.first); if(pos==s.end() || *pos>p.second){ cout << "NO"; return 0; }else{ s.erase(pos); } } cout<<"YES"; } ``` This C++ code snippet demonstrates how to implement the described logic efficiently with appropriate data structures like `std::set` for maintaining unique elements automatically sorted.

阅读全文