Pues pongo uno que es bastante conocido pero que es interesante si no se conoce.

Reto #12
Año 2546, un ladrón quiere cometer una serie de robos en tiendas. Concretamente, hay N tiendas y para cada una, tras una exitosa tarea de investigación, sabe en qué intervalo de tiempo no hay vigilancia (y podrá cometer el robo).

Nuestro ladrón puede teletransportarse de un sitio a otro de forma instantánea (los coches son cosa del pasado), pero sólo robará una tienda si puede dedicar el intervalo completo sin vigilancia a robarla. Por ejemplo, si tenemos dos tiendas con intervalos [100, 200] y [200, 300], podrá robar las dos (recordemos que se puede teletransportar), pero si fueran [100, 200] y [199, 300] sólo podría robar una de las dos.

Entrada:
Un número N <= 1000, seguido de N líneas. En cada una de estas líneas habrá dos números X Y, indicando que la tienda i-ésima no tiene vigilancia en ese intervalo de tiempo. Se cumplirá que 0 <= X,Y <= 10⁹.

Salida:
El máximo número de tiendas que podrá robar.

Ejemplo:

Entrada:

Salida:

Nota: Por las restricciones que he puesto, se acepta una solución O(N²), que se puede lograr haciendo una dinámica muy sencilla. Este problema de los intervalos es conocido como típico problema greedy, pues existe una solución greedy O(NlogN).

Si te fijas el hizo una pregunta... es de mala educacion no contestarla.

Han pasado tres días y no hay soluciones, así que explico como se resuelve (aunque si se buscaba en Google el nombre del problema tal y como dije, explica en muchos sitios diferentes la solución).

La solución más eficiente es un algoritmo greedy que consiste en ordenar los intervalos por hora de final. Una vez hecho esto, se coge el primero y se va cogiendo el siguiente que no solape con el último cogido.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
 
typedef pair<int, int> PII;
 
bool comp(PII a, PII b) {
    return (a.second < b.second) or (a.second == b.second and a.first < b.first);
}
 
int main() {
    int n;
    cin >> n;
    vector<PII> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end(), comp);
    int cnt = 0, ant = -1;
    for (int i = 0; i < n ; ++i) {
        if (v[i].first >= ant) {
            ++cnt;
            ant = v[i].second;
        }
    }
    cout << cnt << endl;
}
 

El último for de este algoritmo es lineal, por lo que la complejidad se ve dominada por el coste de ordenar, que usando un algoritmo eficiente como por ejemplo Merge Sort deja una complejidad de O(NlogN).

Otra solución menos eficiente pero válida con las restricciones que puse es la dinámica cuadrática que se puede hacer en función de la N, que tiene complejidad O(N²).

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
 
typedef pair<int, int> PII;
 
int main() {
    int n;
    cin >> n;
    vector<PII> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end());
    vector<int> M(n);
    int res = 0;
    for (int i = 0; i < n ; ++i) {
        M[i] = 1;
        for (int j = 0; j < i; ++j) 
            if (v[j].second <= v[i].first) M[i] = max(M[i], M[j] + 1);
        res = max(res, M[i]);
    }
    cout << res << endl;
}
 

La idea de la dinámica es que M[ i] representa el máximo número de intervalos que puedo coger usando el i-ésimo en último lugar. Como están ordenados los intervalos por inicio (en el otro se ordenaba por final), el algoritmo planteado es correcto.

Según las normas tras tres días cualquiera puede poner otro reto, mejor que lo ponga otro, que yo puse este último con intención de que fuera muy sencillo...

Bueno, por ahora no toy seguro si es la mejor forma de hacerlo, sigo trbajando en ello, se que hay otras formas, pero no logro hacerlo aún ya que tengo unos pequeños problemas con sequences y mutable types.

F#

open System
 
//forma 1 dos ciclos no usa funcion externa
let r i j= 
    let mutable t = 0
    for i in i .. j do
        let mutable n = i
        let mutable x = 2
        while n <> 1 do
            if n % 2 = 1 then n <- 3*n+1 else n <-n/2
            if x > t then t <- x
            x <- x + 1
    t
 
//funcion para la forma 2 y 3        
let rec gcd n y =
    if n = 1 then y
    else match n % 2 with
        | 1 -> gcd (3*n+1) y + 1
        | _ -> gcd ( n/2) y + 1
 
 
//forma 2
let r2 i j = 
    let mutable m = 0
    let mutable o = 0
    for i in i .. j do 
        o <- gcd i 1
        if o > m then m <- o
    m
 
//forma 3
let rec r3 i j n= 
    if i = j then n
    else let e = gcd i 1
        r3 (i+1) j (match e > n with |true -> e |_ -> n)
 
let a  = Console.ReadLine() |> int
let b  = Console.ReadLine() |> int
 
printfn "r  %A" (r a b)
printfn "r2 %A" (r2 a b)
printfn "r3 %A" (r3 a b 1)
 
Console.ReadKey(true);
 

EDIT:

PD: Se que la idea es hacerlo en C++, pero es que no tengo más nada que hacer

EDIT 2:
Coloco 2 formas más de hacerlo siguiendo el mismo algoritmo, solo lo hago para aprender F# más nada.
Nota: ghastlyX, estoy pensando en lo que me dijiste, un saludo!