Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

vasco16

Remover intervalos dentro de intervalos

Mensagens Recomendadas

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 .

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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 :) .

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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 ..

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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;
		}
	}

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.