optimal_points.cpp

optimal_points.cpp

#include <algorithm>
#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>
#include <string>
// #include <boost/dynamic_bitset.hpp>

using namespace std;
// using namespace boost;

struct Segment {
  int left, right;

  friend Segment intersection(Segment lhs, Segment rhs) {
    Segment intersection;

    intersection.left = std::max<int>(lhs.left, rhs.left);
    intersection.right = std::min<int>(lhs.right, rhs.right);

    return intersection;
  }

  bool within(Segment rhs)
  {
    return left >= rhs.left && right <= rhs.right;
  }

  friend ostream& operator<< (ostream& out, const Segment& segment) {
    out << "Segment(" << segment.left << ", " << segment.right << ")";

    return out;
  }
};

vector<int> optimal_points(vector<Segment>& segments) {
  vector<int> points;
  vector<Segment> intersections;

  // Sort segments by left endpoint
  std::sort(segments.begin(), segments.end(), [](Segment& a, Segment& b) { return a.left < b.left; });

  Segment last_segment = segments[0];
  Segment last_intersection;
  cout << last_segment << last_intersection;

  // Calculate intersections by iterating through segments in left end point order
  for (auto sit = segments.begin() + 1; sit != segments.end(); sit++) {
    Segment current_segment = *sit;
    Segment current_intersection = intersection(last_segment, current_segment);
    cout << "current_segment " << current_segment << " current_intersection " << current_intersection << endl;

    // Intersection is associative.
    // If the intersection is within the last intersection, keep intersecting.
    if (current_intersection.within(last_intersection)) {
      cout << "Current intersection is within last intersection" << endl;
      last_intersection = intersection(last_intersection, current_intersection);
      cout << "last_intersection " << last_intersection << endl;
    } else { // Otherwise, start a new intersection.
      cout << "Current intersection is within last intersection" << endl;
      intersections.push_back(last_intersection);
      last_intersection = current_intersection;
      cout << "last_intersection " << last_intersection << endl;
    }
    last_segment = current_segment;
  }
  intersections.push_back(last_intersection);

  // Place points in each intersection
  for (auto& intersection : intersections) {
    points.push_back(intersection.left);
  }

  return points;
}

// vector<int> optimal_points_exponential(vector<Segment>& segments) {
//   vector<int> points;
//   vector<int> best_points;

//   // Sort segments by left endpoint
//   std::sort(segments.begin(), segments.end(), [](Segment& a, Segment& b) { return a.left < b.left; });

//   // Every line segment either has a point in it or it doesn't.
//   // So create a bitstring of the same length as segments, and iterate through every possible bitstring.
//   // If not every segment contains a point, that solution is invalid.
//   for (int i = 0; i < 1 << (segments.size() - 1); i++) {
//     dynamic_bitset<> bs(segments.size(), i);
//     // Construct a solution
//     for (int j = 0; j < segments.size(); j++) {
//       if (bs[j]) {
//         points.push_back(segments[j].left);
//       }
//     }

//     bool invalid = false;
//     // Check if it's valid
//     int point_idx = 0;
//     for (int j = 0; j < segments.size(); j++) {
//       // If no point is within the segment, the solution is invalid.
//       while (point_idx < segments.size() && points[point_idx] < segments[j].left)
//         point_idx++;
      
//       if (points[point_idx] < segments[j].left || points[point_idx] > segments[j].right) {
//         invalid = true;
//       }
//     }
//     if (invalid)
//       continue;

//     // Check if it's better than the last one. If so, save it.
//     if (points.size() < best_points.size()) {
//       best_points = points;
//     }
//   }
//   return best_points;
// }

int main_test() {
  vector< vector<Segment> > test_cases = {
    // {
    //   {0, 5}, {1, 3}
    // },
    // {
    //   {0, 5}, {1, 6}
    // },
    // {
    //   {0, 6}, {1, 5}, {2, 4}
    // },
    // {
    //   {0, 5}, {1, 3}, {6, 8}
    // },
    {
      {1, 3}, {2, 5}, {3, 6}
    }
  };

  for (auto test_case : test_cases) {
    vector<int> points = optimal_points(test_case);
    for (int point : points) {
      cout << point << " ";
    }
    cout << endl;
  }

  return 0;
}

int main_io() {
  int n;
  cin >> n;
  vector<Segment> segments(n);
  for (size_t i = 0; i < segments.size(); ++i) {
    cin >> segments[i].left >> segments[i].right;
  }
  vector<int> points = optimal_points(segments);
  cout << points.size() << "\n";
  for (size_t i = 0; i < points.size(); ++i) {
    cout << points[i] << " ";
  }
  cout << "\n";
}

int main()
{
  main_test();
}