Problema Spectacolelor

Cerință:

Într-o sală, într-o zi, trebuie planificate n spectacole. Pentru fiecare spectacol se cunoaşte ora de începere (start[i]) şi durata spectacolului (durata[i]). Se cere să se planifice un număr maxim de spectacole astfel încât să nu se suprapună.

Indicații de rezolvare:

Să considerăm A = mulţimea iniţială de spectacole şi B = mulţimea spectacolelor ce vor fi alese.
Pentru a rezolva problema prin tehnica Greedy, prelucrarea care se va face asupra mulţimii A este o ordonare crescătoare după ora de finalizare.
Apoi se iau spectacolele în ordine, astfel încât fiecare spectacol să înceapă după ce s-a terminat cel anterior lui.

Implementare:

Cod Sursa C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace PbSpectacolelor
{
    class Program
    {
        static void Schimba(double x, double y)
        {
            double aux;
            aux=x; 
            x=y;
            y = aux;
        }
        static void Main(string[] args)
        {
            int n; //numarul de spectacole
            double[] start = new double[100];
            double[] durata = new double[100];
            int i, j;
            double[] a = new double[100]; //permutarea spectacolelor
            double ora_sf; //ora ultimului spectacol
            Console.WriteLine("Problema Spectacolelor");
            Console.WriteLine("**********************");
            Console.WriteLine("Dati numarul de spectacole");
            n = Convert.ToInt32(Console.ReadLine());
            for (i = 1; i <= n; i++)
            {
                Console.WriteLine("Spectacolul cu numarul " + i + ": ");
                Console.Write(" - Ora de incepere: ");
                start[i] = Convert.ToDouble(Console.ReadLine());
                Console.Write(" - Durata lui: ");
                durata[i] = Convert.ToDouble(Console.ReadLine());
                a[i] = i; //permutarea identica
            }
            // se ordoneaza crescator spectacolele dupa ora de terminare
            for (i=1; i<=n-1; i++)
                for (j = i + 1; j <= n; j++)
                {
                    if (start[i] + durata[i] > start[j] + durata[j])
                    {
                        Schimba(start[i],start[j]);
                        Schimba(durata[i],durata[j]);
                        Schimba(a[i], a[j]);
                    }
                }
            Console.WriteLine("Solutie: ");
            ora_sf=start[1]+durata[1];
            Console.WriteLine("Spectacolul " + a[1] + " ");
            i = 2;
            while (i <= n)
            {
                if (ora_sf <= start[i])
                {
                    Console.WriteLine("Spectacolul " + a[i] + " ");
                    ora_sf=start[i]+durata[i];
                }
                i = i + 1;
            }
            Console.ReadLine();
        }
    }
}

Cod Sursa VB

Module Module1
    Sub Schimba(ByVal x As Double, ByVal y As Double)
        Dim aux As Double
        aux = x
        x = y
        y = aux
    End Sub
 
    Sub Main()
        Dim n As Integer
        Dim start(100) As String
        Dim durata(100) As String
        Dim i, j As Integer
        Dim a(100) As String
        Dim ora_sf As Double
        Console.WriteLine("Problema Spectacolelor")
        Console.WriteLine("**********************")
        Console.WriteLine("Dati numarul de spectacole")
        n = Convert.ToInt32(Console.ReadLine())
        For i = 1 To n
            Console.WriteLine("Spectacolul cu numarul " & i & ": ")
            Console.Write(" - Ora de incepere: ")
            start(i) = Convert.ToDouble(Console.ReadLine())
            Console.Write(" - Durata lui: ")
            durata(i) = Convert.ToDouble(Console.ReadLine())
            a(i) = i 'permutarea identica
        Next i
        For i = 1 To n - 1
            For j = i + 1 To n
                If (start(i) + durata(i) >= start(j) + durata(j)) Then
                    Schimba(start(i), start(j))
                    Schimba(durata(i), durata(j))
                    Schimba(a(i), a(j))
                End If
            Next j
        Next i
        Console.WriteLine("Solutie: ")
        ora_sf = Val(start(1)) + Val(durata(1))
        Console.WriteLine("Spectacolul " & a(1) & " ")
        i = 2
        While i <= n
            If (ora_sf <= start(i)) Then
                Console.WriteLine("Spectacolul " & a(i) & " ")
                ora_sf = Val(start(i)) + Val(durata(i))
            End If
            i = i + 1
        End While
        Console.ReadLine()
    End Sub
 
End Module

Cod Sursa C++

#include "stdafx.h"
#include <iostream>
#include <conio.h>
 
using namespace std;
 
void schimba(double x, double y)
{
	double aux;
	aux=x; 
	x=y;
	y = aux;
}
 
void main()
{
	int n; //numarul de spectacole
	double start[100];
	double durata[100];
	int i, j;
	double a[100]; //permutarea spectacolelor
	double ora_sf; //ora ultimului spectacol
	cout<<"Problema Spectacolelor"<<endl;
	cout<<"**********************"<<endl;
	cout<<"Dati numarul de spectacole: "; cin>>n;
	for (i = 1; i <= n; i++)
	{
		 cout<<"Spectacolul cu numarul "<< i << ": "<<endl;
		 cout<<" - Ora de incepere: ";
		 cin>>start[i];
		 cout<<" - Durata lui: ";
		 cin>>durata[i];                
		 a[i] = i; //permutarea identica
	}
	// se ordoneaza crescator spectacolele dupa ora de terminare
	for (i=1; i<=n-1; i++)
		for (j = i + 1; j <= n; j++)
		{
			if (start[i] + durata[i] > start[j] + durata[j])
			{
				 schimba(start[i],start[j]);
				 schimba(durata[i],durata[j]);
				 schimba(a[i], a[j]);
			}
		}
	cout<<"Solutie: "<<endl;
	ora_sf=start[1]+durata[1];
	cout<<"Spectacolul " << a[1] << " "<<endl;
	i = 2;
	while (i <= n)
	{
		 if (ora_sf <= start[i])
		 {
			   cout<<"Spectacolul " << a[i] << " "<<endl;
			   ora_sf=start[i]+durata[i];
		 }
		 i = i + 1;
	}
	system("pause");
}

Rezultat: