Sumowanie przedziałów - mała złożoność

Question

Witam, dostałem zadanie w którym na wejściu dostaję liczbę całkowitą n oraz poniżej n par liczb. W każdej parze pierwsza liczba to początek a druga to koniec przedziału. Moim zadaniem jest wypisanie liczby l (ile przedziałów udało sie stworzyć po zsumowaniu przedziałów z wejścia) oraz właśnie te zsumowane przedziały. Zrobiłem to zadanie ze złożonością czasową n^2, a potrzebuję jakiegoś rozwiązania z mniejszą złożonością (najlepiej liniową). Kompletnie nie mam żadnego pomysłu jak to zrobić aby złożoność była mniejsza niż n^2. Proszę o pomoc. Piszę to w C++.
Przykład:
we:
2
1 3
2 5
wy:
1
1 5

Comments

nie znam się na algorytmach, ale taki pomysł, tylko nie wiem czy złożoność będzie mniejsza

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <map>

using namespace std;

int main()
{
    std::map<int,char> m;
    m[2]='(';
    m[3]=')';
    m[1]=')';
    for(auto &x:m )
    {cout<<x.first<<'\t'<<x.second<<endl ; 
   // ...
    //case '(':if(temp==current) erase.current // pseudo code
    //case ')':if(temp==current) erase.temp // pseudo code
   // ...
    }
    return 0;
}
//https://en.cppreference.com/w/cpp/container/map
//https://en.cppreference.com/w/cpp/container/map/erase

 

---

@Perkol02, hint: posortuj po poczatku przedziału

Answer 1

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

int main() {
    std::uniform_int_distribution<int> dist1(1, 100);
    std::uniform_int_distribution<int> dist2(1, 10);
    std::default_random_engine gen(std::random_device{}());

    using Interval = std::pair<int, int>;
    std::vector<Interval> inputs(8);
    for (auto& [min, max] : inputs) {
        min = dist1(gen);
        max = min + dist2(gen);
        std::cout << min << " " << max << "\n";
    }

/////////////////////////////////////////////////////////////////////////////////////////////

    std::ranges::sort(inputs); // O(n log n) // lub std::sort(inputs.begin(), inputs.end())
 
    std::vector<Interval> merged(1, inputs.front());
    for (auto [min, max] : inputs) {
        auto& [lastMin, lastMax] = merged.back();
        if (lastMax < min) {
            merged.emplace_back(min, max);
        } else {
            lastMax = std::max(lastMax, max);
        }
    } // O (n)

/////////////////////////////////////////////////////////////////////////////////////////////
    
    std::cout << std::string(10, '-');
    for (auto& [min, max] : merged) {
        std::cout << "\n(" << min << " " << max << ")";
    }
}

Answer 2

Zastosowałem się do swoich rad i nie działało. To napisałem taki kod, też nie działa ale już lepiej (może mniej niż n^2)

#include <iostream>
#include <map>
#include <vector>
#include <ctime>
#include <random>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <iterator>
#include <numeric>

using namespace std;

int main()
{
	////////////////////////////////////////////////
    uniform_int_distribution<int> d1 ( 1, 100 );
    uniform_int_distribution<int> d2 ( 1, 10 );
    default_random_engine gen ( time ( NULL ) );
    vector <int> vec(40);
    
    for (int i=0; i< vec.size()-1;i+=2) {
         vec[i]=d1(gen); vec[i+1]=vec[i]+d2(gen);
    }
    for (int i=0; i< vec.size()-1;i+=2) 
         std::cout<<vec[i]<<' ' <<vec[i+1]<<'\n';
         
 ////////////////////////////////////////////////////        
    std::multimap<int,char> m;
    std::multimap<int,char> mout;
    
    
    for (int i=0; i< vec.size()-1;i+=2){
    	// m[vec[i]]='('; //nie działa
    	// m[vec[i+1]]=')'; //nie działa
    	m.insert(std::pair<int,char>{vec[i], '('});
    	m.insert(std::pair<int,char>{vec[i+1], ')'});
    }
    for(auto &x:m ) {cout<<setw(3)<<x.second<<' '; }
   	 cout<<endl;
    for(auto &x:m ) {cout<<setw(3)<<x.first<<' '; }
    	 cout<<endl;  
     int i=0;
     
     //////////////////////////////////////////////////////
     for(auto it=m.begin();it!=m.end();it++){
    	 mout.insert(*it);
     	do {
     		if (it->second=='('){i++;}
     		else i--; 
     	//	cout<<i<<endl;
     		if (i==0) break;
     		it++;
	}while (1);
     	mout.insert(*it);
     }
    for(auto &x:mout ) {
    	if (x.second == '(') cout<<setw(3)<<x.second<<x.first<<','; 
    	else cout<<setw(3)<<x.first<<x.second<<';'; }
    
    return 0;
}

PS. Sorki za wypowiedz.

Comments

Podpowiedź z posortowaniem okazała się bardzo przydatna. Zrobiłem vector par, gdzie każda para to jeden przedział, posortowałem te pary i potem wystarczyło już tylko porównywać koniec przedziału z początkiem następnego + kilka specjalnych przypadków, więc kilka if’ów. Złożoność wyszła liniowa w takim rozwiązaniu. Dziękuje wszystkim za pomoc :))