C语言区间覆盖

#include<stdio.h>

#include <stdlib.h>

#define N 10000

typedef struct{

int head

int nail

} NODE

NODE a[N]

int n

int cmp(const void *a,const void *b){

return ((NODE*)a)->head - ((NODE*)b)->head

}

int main ()

{

scanf("%d",&n)

while(n!=0){

int i

for(i=0i<ni++)

scanf("%d%d",&a[i].head,&a[i].nail)

qsort(a,n,sizeof(a[0]),cmp)

for(i=0i<n-1i++){

while(a[i].nail>a[i+1].head){

if(a[i].nail>a[i+1].nail){

a[i+1].head = a[i].head,a[i+1].nail = a[i].nail

//a[i].nail = a[i].head

}else{

a[i+1].head = a[i].head

}

a[i].nail = a[i].head

i++

}

}

int sum = 0

for(i=0i<ni++) sum+=a[i].nail - a[i].head

printf("%d\n",sum)

scanf("%d",&n)

}

return 0

}

这样就可以了

我采用贪心的算法,

按照左端点排序,

建立一个以线段右端点为关键字的大根堆.

依次尝试插入线段,

对于当前的一个线段,

如果能够覆盖,显然我们选择覆盖,

而如果不能覆盖,

我们进行一下讨论.

首先我们需要知道

(1)

如果线段发生相交,

那么只可能是两条线段相交:

理由:

对于前面的所有线段,贪心法保证,也显然,已经满足两两不相交了,

那么如果当前的线段,和另外两条线段相交,

则必然将一条线段包含,

而我们按照线段左端点排序,

按次序尝试覆盖,

因此这种情况是不存在的.

那么我们假设当前的线段是

[L0,

R0]

发生相交的线段是

[L1,

R1]

即有

L0

>=

L1

R0

<=

R1

这两条线段是不能共存的.

显然,我们要从中留下一个而舍去一个,

舍去哪个呢?

就应该选择右端点小的那个!

为什么?

因为右端点越靠左,对后面的线段的覆盖产生的影响(就是发生覆盖的机会)就越小!

很直观的,

我们可以知道这种贪心法的正确性.

问题就解决了

时间复杂度

O(N

log

N)

我写的代码:

#include<cstdio>

#include<vector>

#include<queue>

#include<algorithm>

using

namespace

std

const

int

maxn

=

10010

struct

event

{

int

l,

r

}e[maxn]

struct

__Comp

{

inline

int

operator()

(const

event

&a,

const

event

&b)

const

{

return

a.r

<

b.r

}

}

priority_queue<event,

vector<event>,

__Comp>

hp

int

n,

l,

r

inline

int

comp(const

event

&a,

const

event

&b)

{return

a.l

<

b.l}

int

main()

{

scanf("%d",

&n)

for

(int

i=0i<n++i)

{

scanf("%d

%d",

&l,

&r)

e[i]

=

(event){l<?r,

l>?r}

}sort(e,

e+n,

comp)

for

(int

i=0i<n++i)

{

if

(!i)

{hp.push(e[0])

continue}

if

(e[i].l

>=

hp.top().r)

hp.push(e[i])

else

if

(hp.top().r

>

e[i].r)

{

hp.pop()

hp.push(e[i])

}

}

printf("%d\n",

hp.size())

scanf("%*s")

}