interval map implementation

You have UB by decrementing begin of the map:

auto beforePrev = prevInterval;
--beforePrev;

Demo

your following test is also strange:

if (beforePrev != m_map.end()

beforePrev cannot be end() as you decrement it.

it seems you can replace that block by

prevInterval->second = val;
if (prevInterval != m_map.begin() && !((--prevInterval)->second == val)){
    ++prevInterval;
} 

Demo

A while ago I failed this coding assessment but it's not in my nature to leave tasks unsolved. So here is my solution with some additional context.

The task

The ultimate goal is a data structure that manages intervals called interval_map. Each interval_map<K,V> is defined by two data types (K, V) and a default value (m_valBegin). K is the type of the keys which defines the domain. Each key is associated with a value V. At the start, each key is implicitly associated with the default value m_valBegin.

interval_map<int, char> m{'A'};
// ...
// -2 -> 'A'
// -1 -> 'A'
// -0 -> 'A'
//  1 -> 'A'
// ...

Each interval_map has a class member m_map of type std::map<K,V> that contains markers (key-value-pairs) which indicate beginnings of ranges of values. So, imagine you had initialized map m with default value 'A' like above and wanted to set all keys in range [-1, 2) to 'B', then you would call assign like so:

interval_map<int, char> m{'A'};
m.assign(-1, 2, 'B');
// assign sets m.m_map -> { (-1, 'B'), (2, 'A') }
// ...
// -2 -> 'A'
// -1 -> 'B'
// -0 -> 'B'
//  1 -> 'B'
//  2 -> 'A'
//  3 -> 'A'
// ...

The task is to implement the assign function and the main challenges are efficiency and adhering to type requirements. Types K and V are copyable and assignable but besides that you are only allowed to assume type K implements operator< and type B implements operator==. Regarding efficiency, it is not sufficient to be big-O optimal (asymptotically optimal) but you are also limited to only one call of amortized O(logn) runtime.

The approach

std::map is implemented as balanced binary search tree. That means that any search for a key within the data structure does already come at a cost of O(logn). Since we are only allowed one O(logn) call, we need to be clever with how we use it.

Imagine the assign(keyBegin, keyEnd, value) function is called with keyBegin=4, keyEnd=11, value='D'. A correct and canonical solution could do the following:

1. The value of the largest marker with key <= keyEnd needs to be remembered for the new end marker (V endMarkerVal).
2. Each previous marker in m_map in the range of [keyBegin, keyEnd] is deleted.
3. The new begin and end markers are inserted with the right values.

Some care needs to be taken with edge cases, e.g. m_map boundaries (begin() and end()), extensions of ranges with same values or default values (e.g. m.assign(1, 4, 'C'), m.assign(4, 6, 'C') -> don't insert second begin marker at 4), etc.

But how to adhere to the runtime requirements?

1. Just use one O(logn) call of m_map.upper_bound(keyEnd); to get to the first item with key larger than keyEnd.
2. Manually move the iterator towards keyBegin, remembering endMarkerVal and deleting markers. (This is worst case O(n) but each inserted marker can only be deleted once and so this is amortized O(1) over the lifespan of the data structure)
3. After deletion, use the iterator as hint to guide insertion to the right place to get amortized O(1) insertion (m_map.insert(it_hint, std::make_pair(keyBegin, val));).

Testing

Test your solution against the one by Amila Senadheera. As far as I can tell this is the only correct one posted here, though it doesn't fulfill the runtime requirements. Here is a simple randomized test function. Just create the assignCorrect() function with Amila's code to compare it against your assign() function.

void randomTest() {
    srand(time(0));
    interval_map<int, char> m1{'A'};
    interval_map<int, char> m2{'A'};
    std::vector<std::tuple<int, int, char>> inputs;

    for(int i = 0; i < 1000; i++) {
        int keyBegin = rand() % 2000 - 1000;
        int keyEnd = keyBegin + rand() % 1000;
        char c = 'A' + rand() % 26;
        inputs.push_back( std::tuple<int, int, char>(keyBegin, keyEnd, c) );
    }

    for(auto [keyBegin, keyEnd, c] : inputs) {
        m1.assign(keyBegin, keyEnd, c);
        m2.assignCorrect(keyBegin, keyEnd, c);

        if(m1.print() != m2.print()) {
            std::cout << "Incorrect solution!" << std::endl;
            return;
        }
    }
}

Note that even if your solution is correct, you should triple check all the type and runtime requirements!

The code

Finally, I want to share my actual code, which I believe to fulfill all the requirements. I didn't get the chance to submit it myself, as I failed my first two submissions. I would suggest you use it only if you fail the assignment too, to get a sense of what you might have missed.

void assign( K const& keyBegin, K const& keyEnd, V const& val ) {
    // empty interval, note: >= might not be implemented for K
    if(!(keyBegin < keyEnd))
        return;
    
    // pointing to first element with key > keyEnd (won't be deleted by erase)
    const auto it_end = m_map.upper_bound(keyEnd); // single O(logn) call

    V endMarkerVal = m_valBegin;
    auto it_start = it_end; // needed for special case it_end == m_map.end() where it_start->first would be meaningless
    if(it_end != m_map.begin()) {
        it_start--;
        endMarkerVal = it_start->second; // just one copy constructor call for V type
    }
        
    // amortized O(1) because each element is deleted at most once
    while(keyBegin < it_start->first && it_start != m_map.begin())
        it_start--;

    // it_start is now <= keyBegin
    // need to make sure we don't delete one element too early
    // but guarantee it_start < it_end so that we don't get exception at erase
    if(it_start->first < keyBegin && it_start != it_end) 
        it_start++;
    
    // helper variables for readability - only == defined for V
    const bool valDiffersFromPreceedingRange = !(it_start != m_map.begin() && std::prev(it_start)->second == val);
    const bool beginMarkerDiffersFromDefault = !(it_start == m_map.begin() && val == m_valBegin);
    
    // only insert beginning of new interval if the new range has a different val (also considering default m_valBegin)
    const bool insertBeginMarker = valDiffersFromPreceedingRange && beginMarkerDiffersFromDefault;
    // only insert beginning of following interval if the range has a different value
    const bool insertEndMarker = !(endMarkerVal == val); // != might not be implemented for V

    // O(n) worst case, amortized O(1) because each element is deleted at most once
    // save iterator for amortized O(1) inserts
    const auto it_hint = m_map.erase(it_start, it_end);

    if(insertBeginMarker)
        m_map.insert(it_hint, std::make_pair(keyBegin, val)); // saves one default construction compared to [] operator

    if(insertEndMarker)
        m_map.insert(it_hint, std::make_pair(keyEnd, endMarkerVal)); // saves one default construction compared to [] operator
}

I hope my post could support you in solving the problem yourself or getting a better feel for it. If that was the case or if you find potential improvements to my solution, please let me know. It would make me very happy :)

First write test code: This is to test the type requirements

class Value {

char a;

public:
        Value(char _a){ a = _a; }

        bool operator==(const Value& _val) const;
        friend ostream& operator<<(ostream& os, const Value& val); //  ONLY FOR TESTING, NOT RELATED TO SOLUTION

};

bool Value::operator==( const Value& _val ) const{
return ( a == _val.a ) ;
}

// operator<< is implemented ONLY FOR TESTING PURPOSE
ostream& operator<<(ostream& os, const Value& val)
{
    os << val.a;
    return os;
}

class Key {

int a;

public:
        Key(int _a){ a = _a; }
        Key(){ a = 0; }
        bool operator<(const Key& _key) const;
        friend ostream& operator<<(ostream& os, const Key& _key); //  ONLY FOR TESTING, NOT RELATED TO SOLUTION


};


bool Key::operator<( const Key& _key ) const{
return ( a < _key.a ) ;
}


// operator<< is implemented ONLY FOR TESTING PURPOSE
ostream& operator<<(ostream& os, const Key& _key)
{
    os <<  _key.a;
    return os;
}

Now the implementation

void assign( K const& keyBegin, K const& keyEnd, V const& val ) {

        K last = m_map.rbegin()->first;
        K first = m_map.begin()->first;


        if (!(keyBegin < keyEnd) ) return;
        if ( keyBegin < first ) return;
        if( last < keyEnd) return ;

         for (auto it = m_map.begin(); it!=m_map.end(); ++it)
         {
                if((*it).first < keyBegin) continue;
                else
                {
                        (*it).second=val;
                        it++;
                        auto tmp=it;
                        while((*it).first < keyEnd){
                                it++;
                        }
                        m_map.erase(tmp, it);

                break;
                }
         }
    }

Another Solution

void assign( K const& keyBegin, K const& keyEnd, V const& val ) {

        K last = m_map.rbegin()->first;
        K first = m_map.begin()->first;


        if (!(keyBegin < keyEnd) ) return;
        if ( keyBegin < first ) return;
        if( last < keyEnd) return ;

        auto itr1 = m_map.find(keyBegin);
        auto itr2 = m_map.find(keyEnd);

        (*itr1).second=val;
        itr1++;

        m_map.erase(itr1,itr2);

         cout << endl << endl;

    }

I just had the same interview. My approach was different to all above - but worked. I've spent a lot of effort for testing-scenarios. Unfortunately I was using the [] operator for assigning map-values. That required the use of default constructor - which apparently was not allowed (nowhere clearly stated though). Despite the fact they recommended testing with <int, char> - which of course both have default constructor.

Your solution is wrong, you have to delete every subinterval that is contained on the new interval.

also the employer requested to use at most only one function maximum to be log(n), the upper_bound and lower_bound are log(n), and inserttion also without a hint. you have to always keep the iterator for the hint to be constant time.

this code passes (with all the requirements for canonicity and types of v and k).

enter code here
void assign( K const& keyBegin, K const& keyEnd, V const& val ){
    if(!(keyBegin < keyEnd))
        return;

    if( m_map.empty() ){
        if( val == m_valBegin )
            return;
        m_map.insert({keyBegin, val});
        m_map.insert({keyEnd, m_valBegin});
        return;
    }


    K end_interval = m_map.rbegin()->first;
    auto iter = m_map.end();
    if( end_interval < keyEnd ){
        m_map.insert( m_map.end(), pair<K,V>( keyEnd, m_valBegin) );
        iter--;iter--;
    } else {
        iter = m_map.lower_bound(keyEnd);
        V nextIntervalValue = iter->second;
        if( !(nextIntervalValue == val) ){
            iter = m_map.insert_or_assign( iter, keyEnd, prev(iter)->second );
            iter--;
        }
    }


    while( keyBegin < iter->first  ){
        if(iter == m_map.begin()){
            m_map.erase(iter);
            break;
        }
        m_map.erase(iter--);
    }

    K begin_interval = m_map.begin()->first;
    if(keyBegin < begin_interval){
        if( !(val == m_valBegin) )
            m_map.insert_or_assign(  m_map.begin(),keyBegin, val );
    } else {
        V previousIntervalValue = (--iter)->second;
        if( !(val == previousIntervalValue ) )
        m_map.insert_or_assign(  iter, keyBegin, val );
    }
    
}

on main some simple tests:

int main(){

//first test case
interval_map<int, char> fooh { 'z' };
fooh.assign(2,5,'a');
fooh.print();
std::cout << fooh[6] << std::endl << std::endl;

//second test case
// expected : z  b  z
fooh = interval_map<int, char>{'z'};
fooh.assign(1,4,'b');
cout << fooh[0] << " " << fooh[1] << " " << fooh[5] << endl; 

//third test case
// expected: A
fooh = interval_map<int, char>{'z'};
fooh.assign(1,6,'A');
fooh.assign(2,4,'B');
cout << fooh[5] << endl;
fooh.print();


//forth test case
fooh = interval_map<int, char>{'z'};
//expected [0,'a'],[1,'z']
fooh.assign(0,1,'a');
fooh.print();


//fifth test case
// expected [0,'f']
fooh = interval_map<int, char>{'z'};
fooh.assign(1,2,'c');
fooh.assign(2,3,'d');
fooh.assign(3,4,'e');
fooh.assign(4,15,'g');
fooh.assign(0,10,'f');
fooh.print();
cout << endl;


//sixth test case
// expected: 0,'d'  2,'c'  
fooh = interval_map<int, char>{'z'};
fooh.assign(1,4,'c');
fooh.assign(0,2,'d');
fooh.print();
cout << endl;

return 0; }

I had this exercise recently. The problem is that they have some ambiguity in the explanation how this "interval map" should work, and they do not provide any test cases, and they only allow you to submit your solution twice. My first submission failed on that my template parameters: Key and Value did not comply, i.e. I used operator == on Key and = (assignment) on value whilst they should not be supported (Key should only support operator < and Value only operator ==). Then I change my implementation and submitted again and they said that either my solution failed on some of their test cases or I do wrongly with iterators (i.e. try to dereference end iterator etc.)

I used gcc compilet test map class instead of stl::map - and this class tests iterators, and they were all fine.

I also wrote an automatic randomised test and it all worked fine.

Now, I think my solution failed because of the ambiguity in the definition of interval_map they provided. They say that if there are no intervals in the map, the default value is: m_valBegin. So suppose it is set to 'A'.

Now, once you insert the first interval, say [10, 20) -> 'B'

Then anything inside this interval is 'B' and anything outside is 'A' - this is my interpretation. So in this interpretation, after the last interval the value will be always identical to the value before the first interval.

However in their description they say: "m_valBegin holds the value that is associated with all keys less than the first key in m_map"

Which sounds differently. But if we assume that m_valBegin is only for values before first interval, then what value will be after the last one? Undefined.

Also their only example is absolutely controversial:

M.m_valBegin=='A',
M.m_map=={ (1,'B'), (3,'A') },
Then M represents the mapping

...
-2 -> 'A'
-1 -> 'A'
0 -> 'A'
1 -> 'B'
2 -> 'B'
3 -> 'A'
4 -> 'A'
5 -> 'A'
...

They on purpose put the second interval value identical to m_valBegin, so it is not possible to understand.

In any case here is my solution which, as I mentioned before, failed. It also includes automatic randomised test. The test inserts into map random intervals and random values and after each insertion it verifies values before, inside and after the interval.

So here is my code:

#include <map>
#include <iostream>
#include <time.h>
#include <cassert>

using namespace std;

template<typename K, typename V>
class interval_map
{
public:
    friend void IntervalMapTest();
    V m_valBegin;
    std::map<K,V> m_map;

    // constructor associates whole range of K with val
    interval_map(V const& val)
    : m_valBegin(val)
    {}

    // Assign value val to interval [keyBegin, keyEnd).
    // Overwrite previous values in this interval.
    // Conforming to the C++ Standard Library conventions, the interval
    // includes keyBegin, but excludes keyEnd.
    // If !( keyBegin < keyEnd ), this designates an empty interval,
    // and assign must do nothing.
    void assign( K const& keyBegin, K const& keyEnd, V const& val )
    {
        if( !(keyBegin < keyEnd) )
        {
            return;
        }

        if( m_map.empty() || (keyEnd < m_map.begin()->first) )
        {
            if(m_valBegin != val)
            {
                m_map.insert({keyBegin, val});
                m_map.insert({keyEnd, m_valBegin});
            }
        }
        else
        {            
            const auto upperBeginKey = m_map.upper_bound(keyBegin);
            const auto upperEndKey = m_map.upper_bound(keyEnd);
            
            assert(upperEndKey != m_map.begin());

            auto keyPostBegin = upperBeginKey;
            
            auto keyBeforeEnd = prev(upperEndKey);

            if( (keyPostBegin != m_map.begin()) && !(prev(keyPostBegin)->first < keyBegin) )
            {
                --keyPostBegin;
            }
            
            assert(keyBeforeEnd != m_map.end());
            
            if( (keyBeforeEnd != m_map.begin()) && !(prev(keyBeforeEnd)->first < keyEnd) )
            {
                ++keyBeforeEnd;
            }
            
            const V valBeforeBeginInt = (keyPostBegin == m_map.begin() ? m_valBegin : prev(keyPostBegin)->second);

            assert(keyBeforeEnd != m_map.end());

            const V valBeforeEndInt = keyBeforeEnd->second;

            m_map.erase(keyPostBegin, next(keyBeforeEnd));
            
            if( !(valBeforeBeginInt == val) )
            {
                m_map.insert( { keyBegin, val } );
            }

            if( !(valBeforeEndInt == val) )
            {
                m_map.insert( { keyEnd, valBeforeEndInt } );
            }
        }
    }

    // look-up of the value associated with key
    V const& operator[]( K const& key ) const
    {
        auto it=m_map.upper_bound(key);

        if(it==m_map.begin())
        {
            return m_valBegin;
        }
        else
        {
            return (--it)->second;
        }
    }

    friend ostream& operator<<(ostream& os, const interval_map& m)
    {
        if(m.m_map.empty())
        {
            os << "empty: " << m.m_valBegin << "\n";
        }
        else
        {
            os << "start:                " << m.m_valBegin << "\n";
            
            auto last_it = prev(m.m_map.end());

            for(auto it = m.m_map.begin(); it != last_it; ++it)
            {
                os << "after  (including): " << it->first << " " << it->second << "\n";
            }

            os << "after  (including): " << last_it->first << " " << last_it->second << "\n";
        }
        
        return os;
    }

    bool validate() const
    {
        bool isOk = true;

        if(!m_map.empty())
        {
            if(m_valBegin == m_map.begin()->second)
            {
                cout << "##### m_valBegin == m_map.begin()->second" << endl;
                isOk = false;
            }

            for(auto it = m_map.begin(); it != prev(m_map.end()); ++it)
            {
                if(it->second == next(it)->second)
                {
                    cout << "##### it->second == next(it)->second" << endl;
                    isOk = false;
                }
            }
            
            if(m_valBegin != prev(m_map.end())->second)
            {
                cout << "m_valBegin != prev(m_map.end())->second" << endl;
                isOk = false;
            }
        }

        return isOk;
    }
};

// Many solutions we receive are incorrect. Consider using a randomized test
// to discover the cases that your implementation does not handle correctly.
// We recommend to implement a test function that tests the functionality of
// the interval_map, for example using a map of int intervals to char.

void IntervalMapTest(const interval_map<int, char>& m, int keyBegin, int keyEnd, char val)
{
    auto m1 = m;
    
    m1.assign(keyBegin, keyEnd, val);

    //cout << "\nm:\n" << m << "\nm1:\n" << m1 << "\n, m.m_valBegin: " << m.m_valBegin << ", keyBegin: " << keyBegin << ", keyEnd: " << keyEnd << ", val: " << val << endl;
    
    if(keyBegin >= keyEnd)
    {
        assert(m1.m_valBegin == m.m_valBegin);
        assert(m1.m_map == m.m_map);
    }
    else
    {
        if(m.m_map.empty())
        {
            assert(m1[keyBegin-1] == m.m_valBegin);
            assert(m1[keyBegin]   == val);
            assert(m1[keyEnd-1]   == val);
            assert(m1[keyEnd]     == m.m_valBegin);
        }
        else
        {
            for(int i = m.m_valBegin - 2; i < keyBegin; ++i)
            {
                assert(m1[i] == m1[i]);
            }
            
            for(int i = keyBegin; i < keyEnd; ++i)
            {
                assert(m1[i] == val);
            }
            
            for(int i = keyEnd; i <= prev(m1.m_map.end())->first; ++i)
            {
                assert(m1[i] == m[i]);
            }
            
            assert(prev(m1.m_map.end())->second == m1.m_valBegin);
        }
    }
    
    assert(m1.validate());
}

class MyKey
{
public:
    MyKey(int key) : key_(key) {}

    MyKey(const MyKey&) = default;
    
    MyKey& operator=(const MyKey&) = default;
    
    bool operator<(const MyKey& other) const
    {
        return key_ < other.key_;
    }
    
    friend ostream& operator<<(ostream& os, const MyKey& k)
    {
        os << k.key_;
        return os;
    }
    
private:
    int key_;
};

class MyVal
{
public:
    MyVal(char val) : val_(val) {}

    MyVal(const MyVal&) = default;
    
    MyVal& operator=(const MyVal&) = default;
    
    bool operator==(const MyVal& other) const
    {
        return other.val_ == val_;
    }
    
    friend ostream& operator<<(ostream& os, const MyVal& val)
    {
        os << val.val_;
        return os;
    }

private:
    char val_;
};

char getRandChar()
{
    return 'A' + (rand() % 26);
}

void IntervalMapTestRandom()
{
    srand(time(NULL));

    interval_map<int, char> m(getRandChar());
    
    for(int i = 0; i < 1000000; ++i)
    {
        const int  keyBegin = rand() % 150;
        const int  keyEnd   = keyBegin + rand() % 150;
        const char val      = getRandChar();
        
        /*cout << "\nbefore:\n" << m << "\n" << "\n";
        
        cout << keyBegin << " " << keyEnd << " " << val << "\n" << "\n";*/
        
        IntervalMapTest(m, keyBegin, keyEnd, val);

        m.assign(keyBegin, keyEnd, val);
    }
    
    cout << m << "\n";
}

int main()
{
    IntervalMapTestRandom();    
}

This solution is CORRECT. But it does more than one log(N) time operations on the std::map (which uses Red-Balck-Tree implementation in the standard library) and this is a sub-optimal solution:

  void assign(K const& keyBegin, K const& keyEnd, V const& val) {
    if (!(keyBegin < keyEnd))
      return;
    V old_end_value = (*this)[keyEnd];
    m_map.erase(m_map.lower_bound(keyBegin), m_map.upper_bound(keyEnd));
    if (m_map.empty() || !((*this)[keyBegin] == val)) {
      m_map.insert({keyBegin, val});
    }
    if (!((*this)[keyEnd] == old_end_value)) {
      m_map.insert({keyEnd, old_end_value});
    }
  }

My approach:

1. Save the old end value of the new range endpoint which might be used in the 4th step.
2. Delete all the boundary values in the map, in the interval [keyBegin, keyEnd).
3. Insert the new start value if that position is not covering the same value already.
4. Insert the new end value only if the old end value has changed (after the third step).

This code generally handles all the cases. Trying to handle different cases specifically, you will miss many edge cases.

if (!(keyBegin < keyEnd))
        return;
    auto upper_bound_end = m_map.upper_bound(keyEnd);
    auto upper_bound_end2 = upper_bound_end;
    upper_bound_end2--;     
    auto uper_bound_begin = m_map.upper_bound(keyBegin);        
    auto uper_bound_begin2 = uper_bound_begin;
    uper_bound_begin2--;
    bool flag = false;
    bool flag2 = false;
    if (!((uper_bound_begin2)->second == val))
        flag = true;
    V tmp;
    if (!((upper_bound_end2)->second == val))
    {
        flag2 = true;
        tmp = (upper_bound_end2)->second;
    }   
    for (auto it = uper_bound_begin; it != upper_bound_end;)
    {
        it = m_map.erase(it);
    }
    if (flag == true)
        m_map[keyBegin] = val;
    if (flag2 == true)
        m_map[keyEnd] = tmp;

This is my solution that can replace the assign function in the question above. The original question was asking for implementing it as a class member function but the question here omitted the class part. So, you can disregard the template and interval_map<K, V> to be able to match the solution in the question, like the other answers in this page.

When implementing, I imagined the assign function as painting a new color over an existing color in a strip. The map here contains only the starting point and the color (i.e. value) in the strip for each painted region.

template <typename K, typename V>
void interval_map<K, V>::assign(const K& keyBegin, const K& keyEnd, const V& val)
{
    using iterator = typename std::map<K, V>::iterator;

    if ( !(keyBegin < keyEnd) )
        return;

    // Handle keyEnd first to not impact the handling of keyBegin.
    iterator it1 = m_map.upper_bound(keyEnd);
    --it1;  // it1 points to the greatest interval whose key <= keyEnd. It exists always.
    V& old_val = it1->second;
    ++it1;
    if ( old_val != val )
        // If old_val from the greatest interval does not equal the desired val, we cut
        // off the interval at keyEnd unless the interval already starts with keyEnd, in
        // which case we do nothing.
        // If old_val equals val we set up to erase up to that interval.
        it1 = m_map.try_emplace(it1, keyEnd, std::move(old_val));
    // Now it1 points to the first interval starting from keyEnd that has a value
    // different than `val`, or m_map.end() if no such interval exits.

    iterator it0 = m_map.lower_bound(keyBegin);
    --it0;  // it0 points to the greatest interval whose key < keyBegin. It exists always.
    if ( it0->second != val )
    {
        // If the greatest interval has a value different than `val`, we create a new
        // interval at keyBegin, or if there already exists an interval starting at
        // keyBegin we change the value.
        // If the greatest interval has `val` as the value we make it our interval to
        // cover [keyBegin, keyEnd).
        ++it0;
        it0 = m_map.insert_or_assign(it0, keyBegin, val);
    }
    // Now it0 points to the first interval that covers keyBegin and has the value `val`.

    // Extend it0 until it1, that is, erase all iterators {it | it0 < it < it1}.
    ++it0;
    m_map.erase(it0, it1);
}

FYI, I also wrote a verify function that can be called after each assign to verify the validity of the whole map. Hope this can help to understand the property of the map to satisfy across assign operations.

template <typename K, typename V>
void interval_map<K, V>::_verify(const K& keyBegin, const K& keyEnd, const V& val) const
{
    // 1. m_map should be non-empty.
    assert( m_map.begin() != m_map.end() );

    auto it = m_map.begin();
    V prev_val = it->second;
    while ( ++it != m_map.end() )
    {
        // 2. Adjacent intervals should have different values.
        assert( prev_val != it->second );
        prev_val = it->second;
    }

    auto it0 = --m_map.upper_bound(keyBegin);
    auto it1 = --m_map.lower_bound(keyEnd);
    // 3. There should be only one interval that covers [keyBegin, keyEnd).
    assert( it0 == it1 );

    // 4. The interval should have the disired value.
    assert( val == it0->second );
}

Here's another working version. Actually it didn't pass the test because there were unknown problems related to behavior. Tested it with around 10 different test sets + implemented Key and Value classes with mentioned assertions, all worked correctly, I've even fixed the default constructor part. I think maybe here's some error related to iterator dereference, but couldn't find it.

    void assign(K const& keyBegin, K const& keyEnd, V const& val) {
        if (!(keyBegin < keyEnd)) {
            return;
        }
        auto initialBegin = m_map.begin();
        auto greaterThanEndKey = m_map.upper_bound(keyEnd);
        if (greaterThanEndKey == initialBegin) {
            auto result = m_map.emplace(keyEnd, m_valBegin);
            if (!result.second) {
                result.first->second = m_valBegin;
            }
            --greaterThanEndKey;
        }
        else {
            --greaterThanEndKey;
            auto result = m_map.emplace(keyEnd, greaterThanEndKey->second);
            if (!result.second) {
                result.first->second = greaterThanEndKey->second;
            }
            ++greaterThanEndKey;
        }
        auto result = m_map.emplace(keyBegin, val);
        if (!result.second) {
            result.first->second = val;
        }
        auto beginKeyIterator = m_map.lower_bound(keyBegin);
        m_map.erase(++beginKeyIterator, greaterThanEndKey);
    }

Got lured like a fool into this, too. What a heartbreaker indeed this was... Here's my fastest, smallest, and most compliant solution so far:

void assign(K const& keyBegin, K const& keyEnd, V const& val) {
    if (!(keyBegin < keyEnd))
        return;
    if (m_map.begin() == m_map.end())
        m_map.insert_or_assign(m_map.begin(), keyEnd, m_valBegin); // avoiding lowest();
    const auto& l = m_map.lower_bound(keyBegin);            // O(log(N))
    auto R = l;
    while (R != m_map.end() && !(keyEnd < R->first)) ++R;   // O(D) is faster than O(log(N) for D << N.
    const auto& r = std::prev(R);                           // r is never at the end.
    m_map.erase(                                            // (B,E) is the erase opened segment
        /* auto& E = */ std::next(                          // E
        l == m_map.begin() || !(std::prev(l)->second == val) ?
        m_map.insert_or_assign(l, keyBegin, val) :
        /* auto& L = */ std::prev(l)),
        /* auto& B = */ r->second == val ? R :              // B
        !(r->first < keyEnd) && !(keyEnd < r->first) ? r :
        m_map.insert_or_assign(R, keyEnd, r->second));
}

I failed the test on Monday night with the following solution which did not pass the compliance test, with the highly misleading message "Type requirements are met: You must adhere to the specification of the key and value type given above."

void assign(K const& keyBegin, K const& keyEnd, V const& val) {
    if (!(keyBegin < keyEnd))
        return;                                      // trivial rejection of degenerated segments.
    // Adding the Z infimum element to the map simplifies the algorithm in that any key value would be guaranteed to have a lower bound.
    const auto& z = std::numeric_limits<K>::lowest();
    if (m_map.begin() == m_map.end())
        m_map.insert(std::make_pair(z, m_valBegin)).first;
    const auto& l = m_map.lower_bound(keyBegin);            // O(log(N))
#if 1
    auto R = l;                                             // lower bound is guaranteed by the Z imfimum. 
    while (R != m_map.end() && !(keyEnd < R->first)) ++R;   // O(D) is faster than O(log(N) for D << N.
#else
    const auto& R = m_map.upper_bound(keyEnd);              // O(log(N)), is slower than O(D) for short [b,e) distances
#endif
    const auto& r = std::prev(R);                           // r is never at the end.
    const auto& E = r->second == val ? R :
        !(r->first < keyEnd) && !(keyEnd < r->first) ? r :
        m_map.insert_or_assign(R, keyEnd, r->second);
    const auto& B = std::next(                              // Culd be made a bit faster if lowest is guaranteed not to be used as a valid key, 
        l == m_map.begin() || !(std::prev(l)->second == val) ? m_map.insert_or_assign(l, keyBegin, val) :
        std::prev(l));
    m_map.erase(B, E);                                      // (B,E) is the erase range.
}

What we need here, is a test framework to compare our solutions, add more unit tests and performance tests. Here is mine so far:

/* 
* Test framework ans attempted solution for the interval_map problem.
* Created: 2024_03_04, Modified: 2024_03_07
*/

#include <map>

/*
Task Description
interval_map<K,V> is a data structure that efficiently associates intervals of keys of type K with values of type V. Your task is to implement the assign member function of this data structure, which is outlined below.
interval_map<K, V> is implemented on top of std::map. In case you are not entirely sure which functions std::map provides, what they do and which guarantees they provide, we provide an excerpt of the C++ standard here:
Each key-value-pair (k,v) in the std::map means that the value v is associated with the interval from k (including) to the next key (excluding) in the std::map.
Example: the std::map (0,'A'), (3,'B'), (5,'A') represents the mapping
0 -> 'A'
1 -> 'A'
2 -> 'A'
3 -> 'B'
4 -> 'B'
5 -> 'A'
6 -> 'A'
7 -> 'A'
... all the way to numeric_limits<int>::max()
The representation in the std::map must be canonical, that is, consecutive map entries must not have the same value: ..., (0,'A'), (3,'A'), ... is not allowed. Initially, the whole range of K is associated with a given initial value, passed to the constructor of the interval_map<K,V> data structure.
Key type K
besides being copyable and assignable, is less-than comparable via operator<
is bounded below, with the lowest value being std::numeric_limits<K>::lowest()
does not implement any other operations, in particular no equality comparison or arithmetic operators
Value type V
besides being copyable and assignable, is equality-comparable via operator==
does not implement any other operations
*/

#define STYLE 2

enum EAalgorithms {
    AMsReference,
    AMsSubmission, 
    AMsFastest,
    ALGMAX
};
const char* algorithms[] = { 
    "AM's Reference",
    "AM's Submission", 
    "AM's Fastest",
};
static int algorithm{ 0 };
static int alg_min = 0;
static int alg_max = ALGMAX;
static int index_op_warnings = 0;

template<typename K, typename V>
class interval_map
{

public:
    std::map<K, V> m_map;
#if STYLE==2
    V m_valBegin;
    // constructor associates whole range of K with val
    interval_map(V const& val)
        : m_valBegin(val)
    {}
    // look-up of the value associated with key
    V const& operator[](K const& key) const {
        index_op_warnings++;
        auto it = m_map.upper_bound(key);
        if (it == m_map.begin())
            return m_valBegin;
        return (--it)->second;
    }
#else
    // constructor associates whole range of K with val by inserting (K_min, val) into the map
    interval_map(V const& val) { m_map.insert(m_map.end(), std::make_pair(std::numeric_limits<K>::lowest(), val)); }
    // look-up of the value associated with key
    V const& operator[](K const& key) const { return (--m_map.upper_bound(key))->second; }
#endif

    // Assign value val to interval [keyBegin, keyEnd).
    // Overwrite previous values in this interval.
    // Conforming to the C++ Standard Library conventions, the interval
    // includes keyBegin, but excludes keyEnd.
    // If !( keyBegin < keyEnd ), this designates an empty interval,
    // and assign must do nothing.
    void assign(K const& keyBegin, K const& keyEnd, V const& val)
    {
        if (!(keyBegin < keyEnd))
            return;                                      // trivial rejection of degenerated segments.

        switch (algorithm)
        {
        case AMsReference:
        {
#if STYLE==2
            if (m_map.begin() == m_map.end())
                m_map.insert_or_assign(m_map.begin(), keyEnd, m_valBegin); // avoiding std::numeric_limits<K>::lowest();
#endif
            auto l = m_map.lower_bound(keyBegin);                  // O(log(N))
            auto R = m_map.upper_bound(keyEnd);                  // O(log(N))
            auto r = std::prev(R);
            m_map.erase(                                    // B 
                std::next(l == m_map.begin() ? m_map.insert_or_assign(l, keyBegin, val) :
                    std::prev(l)->second == val ? std::prev(l) :
                    m_map.insert_or_assign(l, keyBegin, val))
                , 
                r->second == val ? R :                    // E
                !(r->first < keyEnd) && !(keyEnd < r->first) ? r :
                m_map.insert_or_assign(R, keyEnd, r->second)
            );
            break;
        }
        case AMsSubmission:
        {
            //          keyBegin   keyEnd
            //          vvvvvvvvvvvv-
            //          [-----------)            <- interval [b,e) as argument
            //  [-----X----X-----X-------X-----) <- map content
            //  Z     L    l     r       R     end
            //  aaaaaabbbbbccccccbbbbbbbbaaaaaa-

            // Adding the Z infimum element to the map simplifies the algorithm in that any key value would be guaranteed to have a lower bound.
            const auto& z = std::numeric_limits<K>::lowest();
#if STYLE==2
            if (m_map.begin() == m_map.end())
                m_map.insert(std::make_pair(z, m_valBegin)).first;
#endif
            const auto& l = m_map.lower_bound(keyBegin);            // O(log(N))
#if 1
            auto R = l;                                             // lower bound is guaranteed by the Z imfimum. 
            while (R != m_map.end() && !(keyEnd < R->first)) ++R;   // O(D) is faster than O(log(N) for D << N.
#else
            const auto& R = m_map.upper_bound(keyEnd);              // O(log(N)), is slower than O(D) for short [b,e) distances
#endif
            const auto& r = std::prev(R);                           // r is never at the end.
            const auto& E = r->second == val ? R :
                !(r->first < keyEnd) && !(keyEnd < r->first) ? r :
                m_map.insert_or_assign(R, keyEnd, r->second);
            const auto& B = std::next(                              // Culd be made a bit faster if lowest is guaranteed not to be used as a valid key, 
                l == m_map.begin() || !(std::prev(l)->second == val) ? m_map.insert_or_assign(l, keyBegin, val) :
                std::prev(l));
            m_map.erase(B, E);                                      // (B,E) is the erase range.

            //  [-----X-X-----------X----X-----) <- resulting map content
            //  Z     L B           E    R     end
            //  aaaaaabbvvvvvvvvvvvvbbbbbaaaaaa-
            //  0123456789012345678901234567890-
            //  0         1         2         3
            break;
        }
        case AMsFastest:
        {
#if STYLE==2
            if (m_map.begin() == m_map.end())
                m_map.insert_or_assign(m_map.begin(), keyEnd, m_valBegin); // avoiding std::numeric_limits<K>::lowest();
#endif
            //          b           e
            //          vvvvvvvvvvvv-
            //          [-----------)            <- interval [b,e) as argument
            //  [-----X----X-----X-------X-----) <- map content
            //  Z     L    l     r       R     end
            //  aaaaaabbbbbccccccbbbbbbbbaaaaaa-

            const auto& l = m_map.lower_bound(keyBegin);            // O(log(N))
            auto R = l;
            while (R != m_map.end() && !(keyEnd < R->first)) ++R;     // O(D) is faster than O(log(N) for D << N.
            const auto& r = std::prev(R);                           // r is never at the end.
            m_map.erase(                                            // (B,E) is the erase segment, opened at both ends
                /* auto& E = */ std::next(                          // E
                    l == m_map.begin() || !(std::prev(l)->second == val) ?
                    m_map.insert_or_assign(l, keyBegin, val) :
                    /* auto& L = */ std::prev(l)),
                /* auto& B = */ r->second == val ? R :              // B
                !(r->first < keyEnd) && !(keyEnd < r->first) ? r :
                m_map.insert_or_assign(R, keyEnd, r->second));

            //  [-----X-X-----------X----X-----) <- resulting map content
            //  Z     L B           E    R     end
            //  aaaaaabbvvvvvvvvvvvvbbbbbaaaaaa-
            //  0123456789012345678901234567890-
            //  0         1         2         3
            break;
        }
        }
    }
};

// Many solutions we receive are incorrect. Consider using a randomized test
// to discover the cases that your implementation does not handle correctly.
// We recommend to implement a test function that tests the functionality of
// the interval_map, for example using a map of unsigned int intervals to char.

#include <iostream>
#include <windows.h>
//#include <math.h>

class KT
{
    friend std::ostream& operator<<(std::ostream& os, const KT& K);
    unsigned int val;
public:
    static int errors;
    static int warnings;
    KT() : val(0) { errors++; } //KT() = delete;
    constexpr KT(unsigned int val) : val(val) { warnings++; }
    constexpr bool operator<(const KT& other) const { return val < other.val; }
};
int KT::errors = 0;
int KT::warnings = 0;

class KF
{
    friend std::ostream& operator<<(std::ostream& os, const KF& K);
    float val;
public:
    static int errors;
    static int warnings;
    KF() : val(0) { errors++; } //KF() = delete;
    KF(float val) : val(val) { warnings++; }
    bool operator< (KF other) const { return other.val - val > 1.e-4f; }
};
int KF::errors = 0;
int KF::warnings = 0;

class KS
{
    friend std::ostream& operator<<(std::ostream& os, const KS& K);
    std::string val;
public:
    static int errors;
    static int warnings;
    KS() : val("") { errors++; } //KS() = delete;
    KS(const char* cstr) : val(std::string(cstr)) { warnings++; }
    bool operator< (KS other) const { return val < other.val; }
};
int KS::errors = 0;
int KS::warnings = 0;

class VT
{
    friend std::ostream& operator<<(std::ostream& os, const VT& K);
    char val;
public:
    static int errors;
    static int warnings;
    VT() : val(0) { errors++; } //VT() = delete;
    constexpr VT(unsigned int val) : val(val) { warnings++; }
    constexpr bool operator==(const VT& other) const { return val == other.val; }
};
int VT::errors = 0;
int VT::warnings = 0;

std::ostream& operator<<(std::ostream& os, const KF& K) { os << K.val; return os; }
std::ostream& operator<<(std::ostream& os, const VT& V) { os << V.val; return os; }
std::ostream& operator<<(std::ostream& os, const KT& K) { os << K.val; return os; }
std::ostream& operator<<(std::ostream& os, const KS& K) { os << K.val; return os; }

// uncomment to include performance counters 
// #include <windows.h>
#include <assert.h>

void IntervalMapTest()
{
    bool error = false;

#if 1 // These defines are a bit much, but they essentialise the unit tests that follow.
#define START_TEST(name) bool error = false; printf("%30s: ", #name);
#define LENGTH(arr) (sizeof(arr) / sizeof(arr[0]))
#define START_TEST(name) bool error = false; printf("%30s: ", #name);
#define TEST(cond) if (error = !(cond)) printf(" error %s ", #cond)
#define CLEAR_COUNTERS \
    index_op_warnings = 0; \
    KT::errors = KF::errors = KS::errors = VT::errors = 0; \
    KT::warnings = KF::warnings = KS::warnings = VT::warnings = 0;
#define TEST_COUNTERS\
    index_op_warnings && printf("Use of operator [] warning, "); \
    error |= KT::errors && printf("KT default ctor error, "); \
    error |= KF::errors && printf("KF default ctor error, "); \
    error |= KS::errors && printf("KS default ctor error, "); \
    error |= VT::errors && printf("VT default ctor error, "); \
    error |= KT::warnings && printf("KT-ctor warning, "); \
    error |= KF::warnings && printf("KF-ctor warning, "); \
    error |= KS::warnings && printf("KS-ctor warning, "); \
    error |= VT::warnings && printf("VT-ctor warning, ");
#define SET_INTERVALS\
    for (const auto &interval : intervals)\
        m.assign(interval.L, interval.R, interval.Label);
#define TEST_EXPECTATIONS \
    TEST_COUNTERS; \
    for (const auto &exp : expectations)\
        if (!(m[exp.pos] == exp.Label))\
        {\
            std::cout  << std::endl << "\t\t\t m[" << exp.pos << "] = " << m[exp.pos] << "<>" << exp.Label << " ";\
            error = true;\
        }
#define TEST_VERIFY \
    for (auto it = m.m_map.begin(); it != m.m_map.end(); ++it)\
    {\
      auto next = std::next(it);\
      if (next != m.m_map.end() && it->second == next->second)\
      {\
          printf(" Map has duplicated consecutive values. ");\
          error = true;\
          break;\
      }\
    }\
    std::cout << "size: " << m.m_map.size();\
    for (auto entry : m.m_map) \
        std::cout << ", {" << entry.first << "," << entry.second << "}"; \
    printf("%s\n", error ? ", FAIL." : ", ok.");
#define END_TEST {CLEAR_COUNTERS; SET_INTERVALS; TEST_EXPECTATIONS; TEST_VERIFY;}
#endif

    {
        {
            START_TEST(PredefinedTest);
            interval_map<KT, VT> m('A');
            struct { KT L, R; VT Label; } intervals[] = { {1,3,'B'} };
            struct { int pos; char Label; } expectations[] = { {-2,'A'}, {-1, 'A'},  {0,'A'}, {1,'B'}, {2,'B'}, {3,'A'}, {4,'A'}, {5, 'A'} };
            END_TEST;
        }
        {
            START_TEST(Simple);
            interval_map<KT, VT> m('A');
            struct { KT L, R; VT Label; } intervals[] = { {1,3,'B'} };
            struct { KT pos; VT Label; } expectations[] = { {0,'A'}, {1,'B'}, {2,'B'}, {3,'A'} };
            END_TEST;
        }
#if 1
        {
            START_TEST(DistinctSegments);
            interval_map<KT, VT> m('A');
            struct { KT L, R; VT Label; } intervals[] = { {1,3,'B'}, {6,8,'C'} };
            struct { KT pos; VT Label; } expectations[] = { {0,'A'}, {1,'B'}, {2,'B'}, {3,'A'}, {4,'A'}, {5,'A'}, {6,'C'}, {7,'C'}, {8,'A'} };
            END_TEST;
        }
        {
            START_TEST(PyramidUp);
            interval_map<KT, VT> m('A');
            struct { KT L, R; VT Label; } intervals[] = { {1, 6, 'B'}, {3, 5, 'C'} };
            struct { KT pos; VT Label; } expectations[] = { {0,'A'}, {1,'B'}, {2,'B'}, {3,'C'}, {4,'C'}, {5,'B'},{6, 'A'} };
            END_TEST;
        }
        {
            START_TEST(PyramidDown);
            interval_map<KT, VT> m('A');
            struct { KT L, R; VT Label; } intervals[] = { {3, 5, 'B'}, {1, 6, 'C'} };
            struct { KT pos; VT Label; } expectations[] = { {0,'A'}, {1,'C'}, {2,'C'}, {3,'C'}, {4,'C'}, {5,'C'},{6, 'A'} };
            END_TEST;
        }
        {
            START_TEST(GrowRight);
            interval_map<KT, VT> m('A');
            struct { KT L, R; VT Label; } intervals[] = { {1, 5, 'B'}, {3, 6, 'B'} };
            struct { KT pos; VT Label; } expectations[] = { {0,'A'}, {1,'B'}, {2,'B'}, {3,'B'}, {4,'B'}, {5,'B'},{6, 'A'} };
            END_TEST;
        }
        {
            START_TEST(GrowLeftRight);
            interval_map<KT, VT> m('A');
            struct { KT L, R; VT Label; } intervals[] = { {2, 3, 'B'}, {1, 5, 'B'} };
            struct { KT pos; VT Label; } expectations[] = { {0,'A'}, {1,'B'}, {2,'B'}, {3,'B'}, {4,'B'}, {5,'A'} };
            END_TEST;
        }
        {
            START_TEST(OverrideLeft);
            interval_map<KT, VT> m('A');
            struct { KT L, R; VT Label; } intervals[] = { {3, 6, 'C'}, {1, 5, 'B'} };
            struct { KT pos; VT Label; } expectations[] = { {0,'A'}, {1,'B'}, {2,'B'}, {3,'B'}, {4,'B'}, {5,'C'},{6, 'A'} };
            END_TEST;
        }
        {
            START_TEST(OverrideRight);
            interval_map<KT, VT> m('A');
            struct { KT L, R; VT Label; } intervals[] = { {1, 5, 'B'}, {3, 6, 'C'} };
            struct { KT pos; VT Label; } expectations[] = { {0,'A'}, {1,'B'}, {2,'B'}, {3,'C'}, {4,'C'}, {5,'C'},{6, 'A'} };
            END_TEST;
        }
        {
            START_TEST(GrowLeft);
            interval_map<KT, VT> m('A');
            struct { KT L, R; VT Label; } intervals[] = { {3, 5, 'B'}, {1, 4, 'B'} };
            struct { KT pos; VT Label; } expectations[] = { {0,'A'}, {1,'B'}, {2,'B'}, {3,'B'}, {4,'B'}, {5,'A'} };
            END_TEST;
        }
        {
            START_TEST(OverrideRight);
            interval_map<KT, VT> m('A');
            struct { KT L, R; VT Label; } intervals[] = { {2, 5, 'B'}, {5, 8, 'C'}, {4, 5, 'A'} };
            struct { KT pos; VT Label; } expectations[] = { {0,'A'}, {1,'A'}, {2,'B'}, {3,'B'}, {4,'A'}, {5,'C'}, {6, 'C'}, {7, 'C'}, {8, 'A'} };
            END_TEST;
        }
        {
            START_TEST(InbetweenPriorLimits);
            interval_map<KT, VT> m('A');
            struct { KT L, R; VT Label; } intervals[] = { {1, 5, 'B'}, {2, 3, 'B'} };
            struct { KT pos; VT Label; } expectations[] = { {0,'A'}, {1,'B'}, {2,'B'}, {3,'B'}, {4,'B'}, {5,'A'} };
            END_TEST;
        }
        {
            START_TEST(ResetRight);
            interval_map<KT, VT> m('A');
            struct { KT L, R; VT Label; } intervals[] = { {1, 5, 'B'}, {4, 6, 'A'} };
            struct { KT pos; VT Label; } expectations[] = { {0,'A'}, {1,'B'}, {2,'B'}, {3,'B'}, {4,'A'}, {5,'A'} };
            END_TEST;
        }
        {
            START_TEST(SetResetSameInterval);
            interval_map<KT, VT> m('A');
            struct { KT L, R; VT Label; } intervals[] = { {1, 5, 'B'}, {1, 5, 'A'} };
            struct { KT pos; VT Label; } expectations[] = { {0,'A'}, {1,'A'}, {2,'A'}, {3,'A'}, {4,'A'}, {5,'A'} };
            END_TEST;
        }
        {
            START_TEST(RestoreInfimum);
            interval_map<unsigned int, char> m('A');
            struct { unsigned int L, R; char Label; } intervals[] = { {1, 5, 'B'}, {0, 7, 'A'} };
            struct { unsigned int pos; char Label; } expectations[] = { {0,'A'}, {1,'A'}, {2,'A'}, {3,'A'}, {4,'A'}, {5,'A'} };
            END_TEST;
        }
#endif
        {
            START_TEST(DevelopmentTest0);
            interval_map<KT, VT> m('a');
            struct { KT L, R; VT Label; } intervals[] = { {0, 6, 'a'}, {6,10,'b'}, {11, 17,'c'}, {17,25,'b'}, {8,20,'v'} };
            struct { KT pos; VT Label; } expectations[] = { {0,'a'}, {6,'b'}, {7,'b'}, {8,'v'}, {19,'v'}, {20,'b'}, {24, 'b'}, {25, 'a'}, {100, 'a'} };
            END_TEST;
        }
        {
            START_TEST(DevelopmentTest1);
            interval_map<KT, VT> m('A');
            struct { KT L, R; VT Label; } intervals[] = { {3, 6, 'B'}, {2, 5, 'C'}, {4, 7, 'A'} };
            struct { KT pos; VT Label; } expectations[] = { {0,'A'}, {1,'A'}, {2,'C'}, {3,'C'}, {4,'A'}, {5,'A'}, {6, 'A'}, {7, 'A'} };
            END_TEST;
        }
        {
            START_TEST(DevelopmentTest2);
            interval_map<KT, VT> m('A');
            struct { KT L, R; VT Label; } intervals[] = {
                {8, 12, 'B'},
                {2, 12, 'B'},
                {2, 12, 'C'},
                {5, 12, 'C'},
                {4, 10, 'C'},
                {4, 12, 'C'},
                {8, 13, 'A'},
                {6,  9, 'D'},
            };
            struct { KT pos; VT Label; } expectations[] = { {0,'A'}, {1,'A'}, {2,'C'}, {3,'C'}, {4,'C'}, {5,'C'}, {6, 'D'}, {7, 'D'}, {8, 'D'}, {9, 'A'} };
            END_TEST;
        }
        {
            START_TEST(FloatKey);
            interval_map<KF, VT> m('A');
            struct { KF L, R; VT Label; } intervals[] = { {-1, 1, 'B'} };
            struct { KF pos; VT Label; } expectations[] = { {-2.f,'A'}, {-1.1f,'A'}, {-1.f,'B'}, {1.f,'A'}, {1.1f,'A'} };
            END_TEST;
        }
        {
            START_TEST(StringKey);
            interval_map<KS, VT> m('A');
            struct { KS L, R; VT Label; } intervals[] = { {"Alpha", "Beta", 'B'}, {"Delta", "Epsilon", 'C'} };
            struct { KS pos; VT Label; } expectations[] = { {"_LessThanAlpha",'A'}, {"Alpha",'B'}, {"Beta", 'A'}, {"Delta",'C'}, {"Epsilon",'A'}, {"Zeta",'A'} };
            END_TEST;
        }
    }
    const char* perf_tests[] = { "AddRight", "Pyramid", "Skew", "Remove" };
    for (int type = 0; type < LENGTH(perf_tests); type++)
    {
        struct Counter
        {
            double Freq = 0.0;
            __int64 Start = 0;
            Counter()
            {
#ifdef _WINDOWS_
                LARGE_INTEGER li;
                if (!QueryPerformanceFrequency(&li))
                    std::cout << "Cannot obtain a performance counter!\n";
                Freq = double(li.QuadPart);
                QueryPerformanceCounter(&li);
                Start = li.QuadPart;
#endif
            }
            operator double() const
            {
#ifdef _WINDOWS_
                LARGE_INTEGER li;
                QueryPerformanceCounter(&li);
                return double(li.QuadPart - Start) / Freq;
#else
                return 0;
#endif
            }
        };

        START_TEST(PerformanceTest);
        int v = 0;
        int factor = 100;
#ifndef _DEBUG
        factor *= 60;
#endif
        if (type == 0)
        {
            interval_map<KT, VT> m(0);
            const int width = 10;
            const int max_test = 1000 * factor;
            const int expsz = max_test + 1;
            Counter counter;
            for (int i = 0; i < max_test; i++)
                m.assign(i * width, (i + 1) * width, --v);
            std::cout << "AddRight time: " << counter << " m.size: " << m.m_map.size()
                << " expected sz: " << expsz << (m.m_map.size() == expsz ? " okay" : " mismatch") << "\n";
        }
        else if (type == 1)
        {
            interval_map<int, unsigned int> m(0);
            const int max_test = factor * 5000;
            const int expsz = max_test + 1;
            Counter counter;
            for (int i = 0; i < max_test; i++)
                m.assign(i, max_test - i, --v);
            std::cout << "Pyramid  time: " << counter << " m.size: " << m.m_map.size()
                << " expected sz: " << expsz << (m.m_map.size() == expsz ? " okay" : " mismatch") << "\n";
        }
        else if (type == 2)
        {
            interval_map<KT, VT> m(0);
            int sqrtf = (int)sqrt(factor);
            const int max_test = 100 * sqrtf;
            const int max_drift = 100 * sqrtf;
            const int expsz = max_test + max_drift - 1;
            Counter counter;
            for (int k = 0; k < max_drift; k++)
                for (int i = 0; i < max_test; i++)
                    m.assign(k + i, k + max_test - i, --v);
            std::cout << "Skew     time: " << counter << " m.size: " << m.m_map.size()
                << " expected sz: " << expsz << (m.m_map.size() == expsz ? " okay" : " mismatch") << "\n";
        }
        else if (type == 3)
        {
            interval_map<KT, VT> m(0);
            int sqrtf = (int)sqrt(factor);
            const int width = 1;
            const int stride = 10;
            const int max_drift = 100 * sqrtf;
            const int max_test = 100 * sqrtf;
            const int expsz = 3;
            Counter counter;
            for (int k = 0; k < max_drift; k++)
            {
                for (int i = 0; i < max_test; i++)
                    m.assign(k * i * width, k * (i + 1) * width, --v);
                int from = k * (max_test - 1) * width;
                int to = k * (max_test + 1) * width;
                for (int i = max_test; i > 0; i -= stride)
                    m.assign(i, to, --v);
            }
            std::cout << "Remove   time: " << counter << " m.size: " << m.m_map.size()
                << " expected sz: " << expsz << (m.m_map.size() == expsz ? " okay" : " mismatch") << "\n";
        }
    }
}

int main(int argc, char* argv[])
{
    for (algorithm = alg_min; algorithm < alg_max; algorithm++)
    {
        std::cout << algorithms[algorithm] << " algorithm:" << std::endl;
        IntervalMapTest();
    }
}

Here is My approach, the interval_map is unlike the regular map where each key can be accessed through [] operation, and when not found a NULL value is returned, however it'll always return a value which is either the value assigned to the exact key, and if not found the closes and less than the key value is assigned, at first a default value is set, then each time an interval is assigned it has to the determine where to start an where to stop, find the closes and less than the keyEnd value, and assign it to keyEnd so that your value knows where to stop, here is the code for it

void assign( K const& keyBegin, K const& keyEnd, V const& val ) {
    if (keyBegin >= keyEnd)
        return;
    auto it = m_map.find(keyBegin);
    auto ite = m_map.find(keyEnd);
    auto end = m_map.end();
    if (ite == end)
    {
        auto curr = m_map.upper_bound(keyEnd); //find the closest value to keyEnd and less than keyEnd
        if(it==m_map.begin())
            m_map.insert_or_assign(keyEnd, m_valBegin); // assign the default value if no value is assigned
        else
            m_map.insert_or_assign(keyEnd, (--curr)->second); // assign the closest value less than keyEnd
        ite = m_map.find(keyEnd);
    }
    if (it == end)
    {
        m_map.insert(std::pair<K, V>(keyBegin, val));
        it = m_map.find(keyBegin);
    }
    while (it != ite)
    {
        m_map.insert_or_assign(it->first, val);
        it++;
    }
}

Here is one take without using upper/lower_bound() checks. I shortly checked against a normal array and if it is canonical, but didn't check the boundaries. One concern I had was whether the eraseEnd iterator will be invalidated if the lower bound is inserted but according to the standard it should not be the case for std::map. It is not a submitted code, so use the idea at your own risk.

void assign( K const& keyBegin, K const& keyEnd, V const& val ) {
    // incorrect key
    if ( keyEnd < keyBegin )
        return;

    const auto &[ upperBoundItr, upperBoundSuccess ] = m_map.insert( { keyEnd, val } );
    auto eraseEnd = upperBoundItr;

    // upper boundary should be the continuation of the previous range. if it is a new insertion
    // it should have the previous range value. if the insertion was not successful, the value should not change.
    if ( upperBoundSuccess ) {
        upperBoundItr->second = std::prev( upperBoundItr )->second;

        // if it is a new insertion, we need to check if the next boundary has the same value.
        if ( auto n = std::next( eraseEnd ); n != m_map.cend() && n->second == eraseEnd->second )
            m_map.erase( n );
    }

    const auto &[ lowerBoundItr, lowerBoundSuccess ] = m_map.insert_or_assign( keyBegin, val );
    auto eraseStart = std::next( lowerBoundItr );

    // if the end of the range has the same value, the end boundary should be removed.
    if ( lowerBoundItr->second == eraseEnd->second )
        eraseEnd = std::next( eraseEnd );

    // if the previous start boundary has the same value, remove the new duplicate.
    if ( lowerBoundItr != m_map.cbegin() && std::prev( lowerBoundItr )->second == val )
        eraseStart = lowerBoundItr;

    m_map.erase( eraseStart, eraseEnd );
}

This is a proven working solution that passes their automatic verification.

void assign(K const& keyBegin, K const& keyEnd, V const& val) {
  if (!(keyBegin < keyEnd)) {
    return;
  }
  auto i = m_map.lower_bound(keyBegin);
  const V valueBeforeRange = i != m_map.begin() ? std::prev(i)->second : m_valBegin;
  const bool entryExistsAtKeyBegin = i != m_map.end() && !(i->first < keyBegin) && !(keyBegin < i->first);
  V valueBeyondRange{entryExistsAtKeyBegin ? i->second : valueBeforeRange};
  if (!(valueBeforeRange == val)) {
    i = m_map.insert_or_assign(i, keyBegin, val);
  }
  else if (entryExistsAtKeyBegin) {
    i = m_map.erase(i);
  }
  if (i != m_map.end() && !(keyBegin < i->first)) {
    ++i;
  }
  while (i != m_map.end() && !(keyEnd < i->first)) {
    if (std::next(i) == m_map.end() || keyEnd < std::next(i)->first) {
      valueBeyondRange = i->second;
    }
    i = m_map.erase(i);
  }
  if (!(valueBeyondRange == val)) {
    m_map.insert_or_assign(i, keyEnd, valueBeyondRange);
  }
}

See here for the full solution with test cases, etc.

I wouldn't trust anything that script says - let me explain: I just did the same test, my tests worked for <int,char> but upon second submission I got the following message:

"Type requirements: You must adhere to the specification of the key and value type given above. For example, many solutions we receive use operations other than those that are explicitly stated in the task description. We have to reject many solutions because they assume that V is default-constructible, e.g., by using std::map::operator[]."

which I think is completely wrong. I was perplexed since I recalled clearly that I never used std::map::operator[] anywhere and used a copy constructor to record the last value of pair:{keyEnd, T}->T via the interval_map operator []:

const V_ lastV((*this)[keyEnd]); // 1 K copy construction

Later, to test this behaviour, I wrote a class wrapper for T, explicitly annulling out the default constructor:

class v_cell {
private:
    char a;
public:

    // no default constructor!

    v_cell(const v_cell & v): a(v.a) // explicit copy construction
    {
    }

    v_cell(const char& c) : a(c) // explicit initialization
    {
    }

    bool operator == (const v_cell& v)
    {
        return a == v.a;
    }

    char getA()
    {
        return a;
    }
};

and that as for many above gave identical results to <int,char> which have nominal default construction in C++. I tested this v_cell class for initialization via explicit calls to a default constructor and it predictably fails.

As it happens, my answer was incorrect anyway because it was big O sub-optimal so fair does.

Just saying that it wasn't anything to do with "types" however and so I wouldn't lose too much sleep over that script ...

full working code below with test in main () (but employer said incorrect usage of template types)

#define _ITERATOR_DEBUG_LEVEL 2
#define _SECURE_SCL 1
#define _HAS_ITERATOR_DEBUGGING 1

#include <iostream>
#include <iomanip>
#include <cassert>
#include <map>

template<typename K, typename V>
class interval_map {    
    V m_valBegin;
    std::map<K, V> m_map;
public:
    // constructor associates whole range of K with val
    interval_map(V const& val)
        : m_valBegin(val)
    {}

    void assign(std::map<K, V> const& testMap) {
        m_map = testMap;
    }

    // Assign value val to interval [keyBegin, keyEnd).
    // Overwrite previous values in this interval.
    // Conforming to the C++ Standard Library conventions, the interval
    // includes keyBegin, but excludes keyEnd.
    // If !( keyBegin < keyEnd ), this designates an empty interval,
    // and assign must do nothing.


    // look-up of the value associated with key
    V const& operator[](K const& key) const {
        auto it = m_map.upper_bound(key);
        if (it == m_map.begin()) {
            return m_valBegin;
        }
        else {
            return (--it)->second;
        }
    }

    void print() {

        std::cout << '\n' << m_valBegin << '\n';
        for (auto it = m_map.begin(); it != m_map.end(); ++it) {
            std::cout << it->first << ", " << it->second << '\n';
        }
    }

    void assign(K const& keyBegin, K const& keyEnd, V const& val) {
                
        if (!(keyBegin < keyEnd)) return;
        
        if (m_map.empty()) {

            if (m_valBegin == val)
                return;

            m_map.insert({ keyBegin, val });
            m_map.insert({ keyEnd, m_valBegin});
            return;
        }

        auto startIt = m_map.lower_bound(keyBegin);
        bool doErase = true;

        if (startIt == m_map.end())
            doErase = false;

        auto endIt = m_map.upper_bound(keyEnd);

        auto upperVal{ m_valBegin };

        if (endIt == m_map.begin())
            doErase = false;                    
        else
            upperVal = (--endIt)->second;
                
        if (endIt != m_map.end())
            endIt++;

        if(doErase)
            m_map.erase(startIt, endIt);
                
        m_map.insert({ keyBegin, val });
        m_map.insert({ keyEnd, upperVal });

        // ensure canonical - further down

        startIt = m_map.lower_bound(keyBegin);
        
        assert(startIt->second == val);         
        
        // go back to prev interval (it can have value = val)
        if (startIt != m_map.begin()) 
        {
            startIt--;

            // then our inserted value is the first equal to val
            if (startIt->second != val) 
                startIt++;
        }
            
        // skip first repeating value (first one should be left - others deleted)
        if(!(startIt == m_map.begin() && val == m_valBegin))
            startIt++;           
                            
        while(startIt != m_map.end())
        {           
            auto tmpKey = startIt->first;

            if ((startIt++)->second == val)
                m_map.erase(tmpKey);
            else 
                break;
        }
                
    }
};

int main() {
    interval_map<int, char> mymap{ 'a' };

    //mymap.assign({ {10,'c'},{20,'a'},{30,'c'},{40,'i'},{50,'c'},{60,'i'} });  
    //mymap.assign(65, 68, 'z');    mymap.print();

    while (1) 
    {       
        mymap.print();
    
        int start, end;
        char ch;

        std::cout << "\n\n Enter start, end, char: ";
        std::cin >> start >> end >> ch;
        
        mymap.assign(start, end, ch);
    }
    
}

Try this code:

#include <iostream>

#include <map>

using namespace std;

template < typename K, typename V >
  class interval_map {
    std::map < K, V > m_map;

    public:
      // constructor
      interval_map(V
        const & val) {
        m_map.insert(m_map.begin(), std::make_pair(std::numeric_limits < K > ::lowest(), val));
      }

    // insert an interval and value
    void insert(K
      const & keyBegin, K
      const & keyEnd, V
      const & val) {
      // check if the interval is valid
      if (!(keyBegin < keyEnd))
        return;

      // find the entry for the interval start
      auto lb = m_map.lower_bound(keyBegin);
      if (lb != m_map.begin() && (--lb) -> second == val) {
        ++lb;
      }

      // remove all entries in the interval
      auto up = m_map.upper_bound(keyEnd);
      while (lb != up) {
        lb = m_map.erase(lb);
      }

      // insert the new interval
      m_map.insert(lb, std::make_pair(keyBegin, val));
      m_map.insert(up, std::make_pair(keyEnd,
        m_map.find(keyBegin) -> second));
    }

  };