August 29th, 2021

The Weekly Challenge 127: Disjoint Lists (C++ Solutions)

Part 1 of The Weekly Challenge 127: You are given two sets with unique numbers. Write a script to figure out if they are disjoint.

#include <vector>
#include <iostream>
#include <algorithm>
/*
 * You are given two sets with unique numbers.
 * Write a script to figure out if they are disjoint.
*/
class DisjointSets{
    public:
        bool disjoint(std::vector<int>, std::vector<int>);
};

bool DisjointSets::disjoint(std::vector<int> v0, std::vector<int> v1){
    bool found = false;
    std::for_each(v0.begin(), v0.end(),
        [&v1, &found](int &n){
            if(std::find(v1.begin(), v1.end(), n) != v1.end())
                found = true;
        }
    );
    return !found;
}

int main(int argc, char** argv){
    std::vector<int> v0 {1, 2, 5, 3, 4};
    std::vector<int> v1 {4, 6, 7, 8, 9};
    DisjointSets ds;
    std::cout << ds.disjoint(v0, v1) << std::endl;
    std::vector<int> v2 {1, 3, 5, 7, 9};
    std::vector<int> v3 {0, 2, 4, 6, 8};
    std::cout << ds.disjoint(v2, v3) << std::endl;
}


Example output:
$ g++ -o cxx/ch-1 cxx/ch-1.cxx
$ cxx/ch-1
0
1

The Weekly Challenge 127: Conflict Intervals (C++ Solutions)

Part 2 of The Weekly Challenge 127: You are given two sets with unique numbers. Write a script to figure out if they are disjoint.

#include <vector>
#include <iostream>
#include <algorithm>
/*
 * You are given a list of intervals. Write a script
 * to determine conflicts between the intervals.
*/
class ConflictIntervals{
    public:
        std::vector<std::vector<int>> conflicts(std::vector<std::vector<int>>);
};

std::vector<std::vector<int>> ConflictIntervals::conflicts(std::vector<std::vector<int>> v){
    std::vector<std::vector<int>> conflicts;
    std::sort(v.begin(), v.end(),
          [](const std::vector<int> &a, const std::vector<int> &b) {
              return a[1] < b[1];
          }
    );
    for(int i = v.size() - 1; i >= 0; i--){
        for (int j = 0; j < i; j++){
            if(v[i][0] >= v[j][0] && v[i][0] <= v[j][1]){
                conflicts.push_back(v[i]);
                break;
            }
        }
    }

    return conflicts;
}

int main(int argc, char** argv){
    std::vector<std::vector<int>> intervals = {{1, 4}, {3, 5}, {6, 8}, {12, 13}, {3, 20}};
    ConflictIntervals ci;
    std::vector<std::vector<int>> conflicts = ci.conflicts(intervals);
    for(int i=0; i < conflicts.size(); i++){
        std::cout << "[" << conflicts[i][0] << ", " << conflicts[i][1] <<  "]" << " ";
    }
    std::cout << std::endl;
    intervals = {{3, 4}, {5, 7}, {6, 9}, {10, 12}, {13, 15}};
    conflicts = ci.conflicts(intervals);
    for(int i=0; i < conflicts.size(); i++){
        std::cout << "[" << conflicts[i][0] << ", " << conflicts[i][1] <<  "]" << " ";
    }
    std::cout << std::endl;
}


Example output:
$ g++ -o cxx/ch-2 cxx/ch-2.cxx
$ cxx/ch-2
[3, 20] [3, 5]
[6, 9]