13. Shopping

桃扇骨 2022-04-10 04:22 171阅读 0赞

Description

Andy needs your help now! There are shops located on the Da'Jiao Road of Liang'Xiang. She knows that theth mall will be opening from moment time till moment

Imaging that she is the owner of the Da'Jiao Road, she wants to close one of the mall in order to save money. Lets call some malls *naive* if after close it the number of **integer moments** of time when at least one of malls is opening won't decrease.

People in Liang'Xiang will be very upset if Andy has to close an excited mall. Help Andy by telling her the index of some *naive* mall. If there is no any, please print `-1`.

Input

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTIwNzE3NQ_size_16_color_FFFFFF_t_70][]

#include "stdio.h"
    #include "stdlib.h"
    struct _shop
    {
        long open;
        long close;
        long num;
    }shop[200005];
    int comp(const void*p1, const void*p2)
    {
        struct _shop *c = (struct _shop*)p1;
        struct _shop *d = (struct _shop*)p2;
        if(c->open != d->open)
            return c->open - d->open;
        else
            return c->close - d->close;
    }
    
    int main(int argc, char const *argv[])
    {
        int flag = 0;
        long n;
        scanf("%ld", &n);
        for (long i = 0; i < n; i++)
        {
            scanf("%ld %ld", &shop[i].open, &shop[i].close);
            shop[i].num = i+1;
        }
        if(n == 1)
        {
            printf("-1\n");
            flag = 1;
            return 0;
        }
        qsort(shop, n, sizeof(struct _shop), comp);
        for (long i = 0; i < n; i++)
        {
            if(shop[i].open == shop[i+1].open)
            {
                printf("%ld\n", shop[i].num);
                flag = 1;
                break;
            }
        }
        if(flag == 0)
        {
            for (long i = 0; i < n - 2; i++)
            {
                if(shop[i+2].close > shop[i+1].close && shop[i].close+1 >= shop[i+2].open)
                {
                    printf("%ld\n",shop[i+1].num);
                    flag = 1;
                    break;
                }
                if(shop[i].close >= shop[i+1].close)
                {
                    printf("%ld\n",shop[i+1].num);
                    flag = 1;
                    break;
                }
                if(shop[i+1].close >= shop[i+2].close)
                {
                    printf("%ld\n",shop[i+2].num);
                    flag = 1;
                    break;
                }
                if(shop[i].close >= shop[i+2].close)
                {
                    printf("%ld\n",shop[i+2].num);
                    flag = 1;
                    break;
                }
                
            }
        }
        if(flag == 0)
            printf("-1\n");
            return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTIwNzE3NQ_size_16_color_FFFFFF_t_70]: /images/20220403/f2242c2b31e34d939b6ffda78d07a12f.png