Algorithms : complete 01-algorithmic_toolbox 02-greedy_algorithms

1 files changed, 26 insertions, 8 deletions

diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/covering_segments.cpp b/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/covering_segments.cpp
index c8f1fcd..9067dfe 100644
--- a/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/covering_segments.cpp
+++ b/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/covering_segments.cpp
@@ -9,14 +9,31 @@ struct Segment {
   int start, end;
 };
 
-vector<int> optimal_points(vector<Segment> &segments) {
-  vector<int> points;
-  //write your code here
-  for (size_t i = 0; i < segments.size(); ++i) {
-    points.push_back(segments[i].start);
-    points.push_back(segments[i].end);
-  }
-  return points;
+bool _sort(Segment i, Segment j)
+{
+    return (i.end <= j.end);
+}
+
+vector<int> optimal_points(vector<Segment> &segments)
+{
+    vector<int> points;
+
+    std::sort(segments.begin(), segments.end(), _sort);
+
+    while (segments.size() > 0) {
+        int v = segments.at(0).end;
+        segments.erase(segments.begin());
+        points.push_back(v);
+
+        for (std::vector<Segment>::iterator it = segments.begin() ; it != segments.end(); ) {
+            if (it->start <= v && it->end >= v) {
+                segments.erase(it);
+            } else
+                it++;
+        }
+    }
+
+    return points;
 }
 
 int main() {
@@ -31,4 +48,5 @@ int main() {
   for (size_t i = 0; i < points.size(); ++i) {
     std::cout << points[i] << " ";
   }
+  std::cout << '\n';
 }