区間スケジューリング問題の類似問題

Question

はじめに

競技プログラミングについての質問ですが、paizaやある企業のコーディングテストに関連するものではありません。

問題概要

数直線状に(start_i, end_i)がいくつか与えられます。
区間スケジューリングでは、仕事の数を最大にする問題ですが、今回は重なっている区間の重なりの最大値を算出したいです。

自分のコード

vp[i].firstにその区間のstart地点
vp[i].secondにその区間のend地点を入れています。

    vector<pair<int, int>> vp;
    int ans = 0;
    for (int i = 0; i<vp.size(); i++){
        int cnt = 0;
        int sx = vp[i].first;
        int ex = vp[i].second;
        for (int j=0; j<vp.size(); j++){
            if((vp[j].first <= sx && vp[j].second >= sx) || (vp[j].first <= ex && vp[j].second >= ex) || (sx <= vp[j].first && ex >= vp[j].second) || (sx >= vp[j].first && ex <= vp[j].second)){
                sx = max(sx, vp[j].first);
                ex = min(ex, vp[j].second);
                cnt++;
            }
        }
        ans = max(ans, cnt);
    }

質問

このアルゴリズムは計算量で言えば$0(N^2)$となっています。
そもそも、このアルゴリズムは正しいのでしょうか? (一応自分のテストケースをいくつか作ったものではうまくいっているのですが確信はありません)
正しい場合、もっと効率よくできたりしないでしょうか?

[追記]atcoderm leetcode, aojなどで関連問題があれば、教えて欲しいです

Answer 1

まずそのコードの問題は

1 3
7 10
2 6
2 6
4 8
4 8

このような6つの区間が与えられたとき[4, 6]で4つの区間が重なりますが、そのアルゴリズムだと3が出ます。

最大重複数を求めるアルゴリズムであれば、区間の端点をソート(例として小さい順)して、順に区間の左端が来たら重複数に+1、右端が来たら-1としていくことでその地点での重複してる区間の数が出せます。(同じ地点に左端と右端が存在する場合の順序を変えることで閉区間と開区間どちらも対応できる)。
似た問題はあるはずですが、見つかりません。