UVa 10020 - Minimal coverage

  1 /*
  2  Problem link
  3  Type: Greedy - INTERVAL COVERING
  4  Algorithm:
  5      Abridge statement for INTERVAL COVERING problem:
  6          Giving an interval [0..n] for example and a set
  7          of segments. Find the minimum number of segments
  8          whose intervals can cover the whole given interval.
  9  
 10      Solution: Sort the set of segment in increasing order
 11      of their left and decreasing order of their right if
 12      they have the same left end. Traverse the set once,
 13      pick up the segment with the furthest right end.
 14  
 15      Why is this correct? Let's take a look to this simple
 16      proof:
 17      - Let A be the set of segments results by doing the
 18      algorithm above (A has n elements).
 19      - Suppose there exists a set B which can cover the
 20      whole interval and has fewer elements than A
 21      (B has m < n elements).
 22      - For any element i, the current interval covered
 23      by A[1..i] must be larger than B[1..i] because we
 24      always pick the furthest right end for A. Therefore,
 25      the interval covered by A[i+1..n] must be smaller
 26      than B[i+1..m].
 27      - But since B has fewer elements, this mean there
 28      MUST exist at least 1 segment k (i <= k <= n) in B that
 29      B[k] has farther right end than A[k]. This is conflict
 30      with the statement that A always pick the farthest right
 31      end segment. Hence, there is no B at all.
 32  
 33      (This is just my proof, if you has a better one, feel
 34       free to comment).
 35  */
 36  #include <iostream>
 37  #include <cstdio>
 38  #include <cstring>
 39  #include <cmath>
 40  #include <cstdlib>
 41  #include <vector>
 42  #include <algorithm>
 43  
 44  using namespace std;
 45  
 46  /* Segment class has compare operator for sorting */
 47  //=============================================================
 48  class Segment {
 49  public:
 50      int l,r;
 51  
 52      Segment();
 53      Segment(int _l, int _r): l(_l), r(_r) {}
 54  
 55      bool operator<(const Segment &segment) const {
 56          if (this->l < segment.l) return true;
 57          if (this->l == segment.l && this->r > segment.r) return true;
 58          return false;
 59      }
 60      bool operator>(const Segment &segment) const {
 61          if (this->l > segment.l) return true;
 62          if (this->l == segment.l && this->r < segment.r) return true;
 63          return false;
 64      }
 65      bool operator==(const Segment &segment) const {
 66          return (this->l == segment.l && this->r == segment.r);
 67      }
 68  };
 69  
 70  int m;
 71  
 72  /* Function group */
 73  //=============================================================
 74  void readFile(vector<Segment> &result);
 75  bool isNotCut(Segment &segment);
 76  int B_SearchAtX(int x, vector<Segment> &segments);
 77  
 78  //=============================================================
 79  int main()
 80  {
 81      int nTest;
 82      cin >> nTest;
 83      while (nTest--) {
 84          vector<Segment> input;
 85          vector<Segment> output;
 86          readFile(input);
 87          bool failed = false;
 88  
 89          // LeftEnd save the current left end and
 90          // rightEnd save the current right end
 91          int leftEnd = 0, rightEnd;
 92  
 93          // The next index to put in the result
 94          int index = 0;
 95  
 96          // First condition, input size > 0 and the
 97          // left end of the left most one must be in range
 98          if (input.size() > 0 && input[0].l <= 0) {
 99              rightEnd = input[index].r;
100  
101              for (int i = 1; i < (int)input.size(); i++)
102                  // If input[i].l covered the current leftEnd
103                  // |-----------| (current left end here)
104                  //          |-------------| (input[i])
105                  if (input[i].l <= leftEnd) {
106                      if (input[i].r > rightEnd) {
107                          // New right end is input[i].r
108                          rightEnd = input[i].r;
109                          index = i;
110                      }
111                  // Visualization for this case:
112                  // |-----------| (current left end here)
113                  //                |------| (input[i])
114                  } else if (input[i].l > leftEnd && input[i].r > rightEnd) {
115                      // If input[i] is not cut with the current
116                      // covered interval.
117                      if (input[i].l > rightEnd) {
118                          failed = true;
119                          break;
120                      }
121  
122                      // If it is finished (fully covered)
123                      if (input[index].r >= m) break;
124  
125                      // Else update the result
126                      output.push_back(input[index]);
127  
128                      // New leftEnd is current rightEnd
129                      leftEnd = rightEnd;
130  
131                      // New rightEnd is input[i].r
132                      rightEnd = input[i].r;
133                      index = i;
134                  }
135              // Put the final one in
136              output.push_back(input[index]);
137          } else failed = true;
138  
139          if (!failed && rightEnd >= m) {
140              cout << output.size() << endl;
141              for (int i = 0; i < (int)output.size(); i++)
142                  cout << output[i].l << " " << output[i].r << endl;
143          } else cout << 0 << endl;
144          if (nTest > 0) cout << endl;
145      }
146      return 0;
147  }
148  
149  //=============================================================
150  void readFile(vector<Segment> &result) {
151      cin >> m;
152      result.clear();
153      while (true) {
154          int l,r;
155          cin >> l >> r;
156          if (l == 0 && r == 0) break;
157          Segment s(l,r);
158          // Not of not cut is cut! Put it in, for get others
159          // out - range segments
160          if (!isNotCut(s)) result.push_back(s);
161      }
162  
163      // Algorithm sort, your class must have compare operator
164      // otherwise you has to write your own compare function
165      sort(result.begin(), result.end());
166  }
167  
168  /* Check if a segment is not cut with given segment */
169  //=============================================================
170  bool isNotCut(Segment &segment) {
171      return (segment.r < 0 || segment.l > m);
172  }