Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Sign in to follow this  
vasco16

Remover intervalos dentro de intervalos

Recommended Posts

vasco16

Boas pessoal tenho uma matriz com o seguinte formato:

5 13

7 7

7 9

14 24

Em que a primeira coluna corresponde ao inicio de uma string e a segunda coluna ao final.

A minha questão é a seguinte:

Como faço para remover intervalos dentro de intervalos?

Por exemplo: 7 7 começa em 7 e tem comprimento 7 está dentro do 5 13 .

Share this post


Link to post
Share on other sites
Knitter

Tendo em conta o exemplo que deste, pretendias remover as duas linhas de 7 7 e 7 9, visto estarem dentro de 5 13?

A minha primeira abordagem seria percorrer todas as linhas, encontrar as posições onde existem sub-conjuntos, colocar essas posições num qualquer array auxiliar e depois remover todas as posições compactando o array inicial.

Se os exemplos forem tão simples como o que tens, ver se um intervalo está dentro de outro é só ver se o início de um conjunto A é maior que o início de um conjunto B e se o fim do conjunto A é menor que o fim do conjunto B, se ambas as condições forem verdadeiras, A está dentro de B.

Share this post


Link to post
Share on other sites
vasco16

Tendo em conta o exemplo que deste, pretendias remover as duas linhas de 7 7 e 7 9, visto estarem dentro de 5 13?

A minha primeira abordagem seria percorrer todas as linhas, encontrar as posições onde existem sub-conjuntos, colocar essas posições num qualquer array auxiliar e depois remover todas as posições compactando o array inicial.

Se os exemplos forem tão simples como o que tens, ver se um intervalo está dentro de outro é só ver se o início de um conjunto A é maior que o início de um conjunto B e se o fim do conjunto A é menor que o fim do conjunto B, se ambas as condições forem verdadeiras, A está dentro de B.

Por exemplo:

2 10 - A

3 2  - B

o inicio de A nao é maior que B mas B está dentro de A :S

Share this post


Link to post
Share on other sites
Knitter

o inicio de A nao é maior que B mas B está dentro de A :S

O início de B é maior que A e o fim de B é menor que A, logo B está dentro de A, pelo menos é isso que leio na resposta que escrevi antes, mas posso estar a confundir-me todo :) .

Share this post


Link to post
Share on other sites
vasco16

O início de B é maior que A e o fim de B é menor que A, logo B está dentro de A, pelo menos é isso que leio na resposta que escrevi antes, mas posso estar a confundir-me todo :) .

Secalhar li mal :)

Mas imagina este caso:

4 linhas de uma matriz;

As linhas 2 e 3 estão dentro da 1 mas esta ( a 1) está dentro da 4 ou seja o intervalo vai ser só a 4 linha.

Como é que posso fazer? se fizer com um for ele nao vai voltar a a ir buscar a primeira posição ..

Share this post


Link to post
Share on other sites
Knitter

Vais ter de comparar uma posição com todas as restantes. Eventualmente podes tentar optimizar mas, e isto é olhando apenas para os exemplos que deste, vais ter de comparar a primeira posição com todas as outras, a segunda com a primeira, a terceira e restantes, a terceira com a primeira, segunda, quarta e restantes, enfim, vais percorrer esse array várias vezes.

Podes tentar ter o array ordenado antes de tentares encontrar sub-conjuntos, ou de outra forma optimizar a procura.

Share this post


Link to post
Share on other sites
vasco16

Vais ter de comparar uma posição com todas as restantes. Eventualmente podes tentar optimizar mas, e isto é olhando apenas para os exemplos que deste, vais ter de comparar a primeira posição com todas as outras, a segunda com a primeira, a terceira e restantes, a terceira com a primeira, segunda, quarta e restantes, enfim, vais percorrer esse array várias vezes.

Podes tentar ter o array ordenado antes de tentares encontrar sub-conjuntos, ou de outra forma optimizar a procura.

Eu neste momento ainda tenho os dados numa lista, achas que é mais facil operar com uma lista? Ou aconselhas algo estrutura de dados melhor?

Estava  a pensar em fazer algo deste tipo:

int i = 0;
	while(i<lista.size()-3){
		if((lista.get(i) >= lista.get(i+2)) && (lista.get(i+1) <= lista.get(i+3))){
			lista.remove(i+2);
			lista.remove(i+3);
			i+=2;
		}
		else{
			lista.remove(i);
			lista.remove(i+1);
			i+=2;
		}
	}

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.