ETH_Informatik/Informatik_I/Exercise_10/Task_4

Task 4: Decomposing a Set into Intervals

• Task
• Input
• Output
• Solution

Task

Any finite set of integers can be uniquely decomposed as a union of disjoint maximal integer intervals, e.g as the union of non-overlapping intervals which are as large as possible. For example, the set \(X = \{ 1,2,3,5,6,8 \}\) decomposes as \(X = [1,3] cup [5,6] cup [8,8]\). Note that \(X = [1,2] cup [3,3] cup [5,6] cup [8,8]\) or \(X = [1,2] cup [5,6] cup [5,6] cup [8,9]\) are not valid decompositions, as \([1,2]\) and \([3,3]\) are not maximal interval subsets of , and intervals may not repeat.

Write a program that inputs a set of integers, as the (possibly repeating) sequence of its members, and outputs the interval decomposition of the set in ascending order of boundaries.

Reminder: ordered sets can be represented in C++ using the std::set<...> container, in which elements are added using the insert method. Iteration (using iterators) in ordered sets takes place in increasing order.

Hint: You may first define a function that, from two std::set iterators first and last, finds the largest integer interval starting from first and ending before last, and returns an iterator just after this interval.

Input

A set of non-negative integer, given as the sequence of its members followed by a negative integer. The sequence can be in any order and may feature repetitions.

Example:

3 5 8 6 5 3 2 1 -1

Output

The interval decomposition of the input set, with interval given in increasing order of boundaries. The interval decomposition must be given as a parenthesized sequence of intervals, with intervals separated by the character U. Intervals themselves must be given by their lower and upper bound, separated by a comma and parenthesized by brackets, with the lower bound coming first.

Example:

([1,3]U[5,6]U[8,8])

Solution

#include <iostream>
#include <set>

using namespace std;

void find_interval(set<int>::iterator &first, set<int>::iterator &last,
                   set<pair<int, int>> &Interval) {
  if (first == last)
    return;

  int firstElement = *first;
  int curElement = *first;

  while ((++first != last) && (*first - curElement <= 1)) {
    curElement = *first;
  }

  pair<int, int> curInterval = {firstElement, curElement};
  Interval.insert(curInterval);

  find_interval(first, last, Interval);
}

int main() {
  int in;
  set<int> Set;
  set<pair<int, int>> Interval;

  cin >> in;

  while (in >= 0) {
    Set.insert(in);
    cin >> in;
  }

  set<int>::iterator first = Set.begin();
  set<int>::iterator last = Set.end();

  find_interval(first, last, Interval);

  int size = Interval.size();
  int count = 1;

  cout << "(";
  for (pair<int, int> h : Interval) {
    cout << "[" << h.first << "," << h.second;
    if (count < size)
      cout << "]" << "U";
    else
      cout << "]";
    ++count;
  }
  cout << ")";

  return 0;
}

---

Made by JirR02 in Switzerland 🇨🇭