Bonjour,

Je suis bloqué sur une épreuve d'algorithmie

Contrairement à d'autres épreuves, celle-ci n'a pas de section d'aide spécifique, raison pour laquelle je me permets de poster ici.

En terme de complexité, je ne pense pas pouvoir vraiment l'améliorer et ce n'est pas mon objectif. Je passe les derniers tests (les plus "consommateurs") sans aucun soucis (moins de 0.06s).
En revanche, il retourne un résultat faux dans certains cas et je n'ai pas accès aux traces de debug pour savoir quels sont ces cas. Les cas lors desquels il plante comportent plus de 1000 entrées, c'est tout ce que je sais.
Peut-être pouvez-vous m'aider dans mon analyse pour savoir à quel endroit mon algo se plante et quels cas de figures j'ai omis ou mal implémenté?
(je précise, une code avec la solution ne m'intéresse pas, c'est vraiment comprendre ce qui est mauvais dans mon algo qui m'importe)

Résumé:
- input:
--- 1ère ligne: N, un nombre d'intervalles
--- N lignes suivantes: X et Y séparés par un espace, respectivement borne minimale et maximale de l'intervalle
- output:
--- le plus grand nombre d'intervalles contenus dans un seul et même autre
Code c : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// --- Algorithm ----
// We sort coats by 'min' then by 'max'. Once sorted, we just have to iterate once through them.
// c: number of previous elements with same 'min'
// r: reference -> last largest item. if x>r.x && y>r.y, we switch ref
// s: sum -> equals c if new ref, else is incremented
// max: equals the biggest 's'
// You can add the line below at the end of the FOR loop for debug:
//        cout << c << " : " << r << " : " << s << " : " << max << endl;
// --- Example ------
// >> Input:
// 12
// 2 6
// 5 7
// 1 4
// 9 10
// 6 10
// 4 9
// 5 6
// 5 6
// 2 9
// 5 9
// 2 3
// 6 8
// >> Expected output:
// 8
// >> Description:
// Coat   c   r    s  max
// ----- --- ---- --- ---      0  1  2  3  4  5  6  7  8  9  10
// {1;4}  0 : 0  : 0 : 0       .  |========|  .  .  .  .  .  .
// {2;3}  0 : 0  : 1 : 0       .  .  |==|  .  .  .  .  .  .  .
// {2;6}  1 : 2  : 1 : 1       .  .  |===========|  .  .  .  .
// {2;9}  2 : 3  : 2 : 1       .  .  |====================|  .
// {4;9}  0 : 3  : 3 : 1       .  .  .  .  |==============|  .
// {5;6}  0 : 3  : 4 : 1       .  .  .  .  .  |==|  .  .  .  .
// {5;6}  1 : 3  : 5 : 1       .  .  .  .  .  |==|  .  .  .  .
// {5;7}  2 : 3  : 6 : 1       .  .  .  .  .  |=====|  .  .  .
// {5;9}  3 : 3  : 7 : 1       .  .  .  .  .  |===========|  .
// {6;8}  0 : 3  : 8 : 1       .  .  .  .  .  .  |=====|  .  .
// {6;10} 1 : 10 : 1 : 8       .  .  .  .  .  .  |===========|
// {9;10} 0 : 10 : 2 : 8       .  .  .  .  .  .  .  .  .  |==|
// ----------------------
// Result: 8
 
struct Coat {
   int min;
   int max;
 
   bool operator<(const Coat& c) const {
      return (min<c.min || (min==c.min && max<c.max));
   }
};
 
int main() {
   int nbCoats, c=0, r=0, s=0, max=0;
   vector<Coat> stock(0);
 
   // --- Get inputs
   cin >> nbCoats;
 
   for (int i=0; i<nbCoats; ++i) {
      Coat c;     
      cin >> c.min;
      cin >> c.max;    
      stock.push_back(c);
   }
 
   // sort by 'min', then by 'max'
   sort(stock.begin(), stock.end());
 
   // --- Analyze stock
   for (int i=1; i<nbCoats; ++i) {
      if (stock[i].min == stock[i-1].min) {
         ++c;
         if (stock[i].max > stock[r].max) {
            if (s > max) {
               max = s;
            }
            r=i;
            s=c;
         } else {
            ++s;
         }
      } else {
         c=0;
         if (stock[i].max <= stock[r].max) {
            ++s;
         } else {
            if (s > max) {
               max = s;
            }
            r=i;
            s=c;
         }
      }
   }
   if (s > max) {
      max=s;
   }
 
   // --- Display result
   cout << max;
}

Merci à ceux qui se pencheront sur le problème
Cordialement