C++实现电影播放时间段合并算法

本文介绍一个使用C++模板类实现的算法，用于合并电影播放时间表中重叠的时间段。

算法描述

该算法接收一系列电影的开始时间和结束时间作为输入，输出合并后的不重叠时间段。

算法步骤：

输入： 读取电影数量和每个电影的开始和结束时间。
排序： 按照开始时间对所有时间段进行排序。
合并： 遍历排序后的时间段，将重叠的时间段合并成一个新的时间段。
输出： 输出合并后的不重叠时间段。

代码实现

#include<iostream>
using std::cin;
using std::cout;
using std::endl;

template<class Type>
class Movie
{
    private:
        int movie_num;//电影有几部
        Type * start_ptr;//指向输入的电影开始时间
        Type * end_ptr;//指向输入的电影结束时间
        Type * new_start_ptr;//指向输出的电影开始时间
        Type * new_end_ptr;//指向输出的电影开始时间
        int ptr_length;//输入的intervals的个数
    public:
        Movie();
        ~Movie();
        void inport_f();//处理输入
        bool inport_check_f() const;//处理输入是否正确
        void exchage_f(Type& first,Type& second);//处理两个值交换
        void sort_f();//处理时间排序
        void judge_f();//处理逻辑判断
        void export_f() const;//处理输出
};

template<class Type>
Movie<Type>::Movie()
{
    movie_num = 0;
    start_ptr = nullptr;
    end_ptr = nullptr;
    new_start_ptr = nullptr;
    new_end_ptr = nullptr;
    ptr_length = 0;
}

template<class Type>
Movie<Type>::~Movie()
{
    delete[] start_ptr;
    delete[] end_ptr;
    delete[] new_start_ptr;
    delete[] new_end_ptr;
}

template<class Type>
void Movie<Type>::inport_f()
{
    //输入提示
    cout << '输入范例:3(enter)' << endl;
    cout << '0 30 5 10 15 20(enter)' << endl;
    cout << '请以空格为间隔输入对应的数据类型，并首先输入共有几部电影' << endl;

    //进行输入
    while(1)
    {
        bool inport_judge = true;//判断输入的正确与否

        cin >> movie_num;
        ptr_length = 2 * movie_num;
        if(!inport_check_f()) continue;//判断输入错误

        start_ptr = new Type[movie_num];//分配储存开始时间的空间
        end_ptr = new Type[movie_num];//分配储存结束时间的空间

        for (int i = 0; i < ptr_length; i++)
        {
            if((i % 2) == 0) cin >> start_ptr[i / 2];
            else cin >> end_ptr[i / 2];

            inport_judge = inport_check_f();//判断输入是否错误
            if(!inport_judge) break;
        }

        if(inport_judge) break;
    }
}

template<class Type>
bool Movie<Type>::inport_check_f() const
{
    if (cin.fail())
    {
        cout << '输入错误，请重新输入' << endl;
        cin.clear();
        cin.ignore(8888,'\n');
        return false;
    }
    return true;
}

template<class Type>
void Movie<Type>::exchage_f(Type& first,Type& second)
{
    Type temp = first;
    first = second;
    second = temp;
}

template<class Type>
void Movie<Type>::sort_f()//将所有电影按照开始时间从小到大顺序排列
{
   for (int i = 0; i < movie_num; i++)
   {
        for (int j = 0; j < movie_num - i - 1; j++)
        {
           if(start_ptr[j] > start_ptr[j+1])
           {
                exchage_f(start_ptr[j],start_ptr[j+1]);
                exchage_f(end_ptr[j],end_ptr[j+1]);
           }
        }   
   }
}

template<class Type>
void Movie<Type>::judge_f()
{
    new_start_ptr = new Type[movie_num];
    new_end_ptr = new Type[movie_num];
    new_start_ptr[0] = start_ptr[0];
    new_end_ptr[0] = end_ptr[0];
    for (int i = 1; i < movie_num; i++)//初始化
    {
        new_start_ptr[i] = 0;
        new_end_ptr[i] = 0;
    }
    

    for (int i = 1, j = 0; i < movie_num; i++)
    {
        if(new_end_ptr[j] >= start_ptr[i] && new_end_ptr[j] <= end_ptr[i])
            new_end_ptr[j] = end_ptr[i];
        else if(new_end_ptr[j] > end_ptr[i])
            ;
        else
        {
            j++;
            new_start_ptr[j] = start_ptr[i];
            new_end_ptr[j] = end_ptr[i];
        }
    }
    
}

template<class Type>
void Movie<Type>::export_f() const
{
    for (int i = 0; i < movie_num; i++)
    {
        if(new_start_ptr[i] != 0 || new_end_ptr[i] != 0)
            cout << new_start_ptr[i] << ' ' << new_end_ptr[i] << '|';
    }
    
}

int main()
{
    Movie<int> my_movie;//可自行选择数据类型
    my_movie.inport_f();//处理输入
    my_movie.sort_f();//排序后便于判断
    my_movie.judge_f();//进行判断
    my_movie.export_f();//处理输出
}

算法分析

时间复杂度：

排序时间复杂度：O(nlogn)，其中 n 是电影的数量。
合并时间复杂度：O(n)。
总时间复杂度：O(nlogn)。

空间复杂度：

存储输入数据：O(n)。
存储合并后的时间段：O(n)。
总空间复杂度：O(n)。

总结

本文介绍的C++算法能够有效地合并电影播放时间表中的重叠时间段。该算法简单直观，时间复杂度较低，是一个实用的解决方案。